Graph Fundamentals

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// This program reads an undirected, unweighted graph and builds:
5
// - Adjacency matrix A (n x n)
6
// - Degree matrix D (n x n, diagonal)
7
// - Laplacian L = D - A
8
// Input format:
9
// n m
10
// m lines of edges: u v (0-based indices)
11
// If your input is 1-based, subtract 1 from u and v when reading.
12
13
int main() {
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
17
    int n, m;
18
    if (!(cin >> n >> m)) return 0;
19
20
    // Initialize n x n matrix with zeros (O(n^2) space and time to zero it)
21
    vector<vector<int>> A(n, vector<int>(n, 0));
22
23
    for (int e = 0; e < m; ++e) {
24
        int u, v; cin >> u >> v;
25
        if (u < 0 || u >= n || v < 0 || v >= n) {
26
            cerr << "Edge out of range: (" << u << "," << v << ")\n";
27
            return 0;
28
        }
29
        if (u == v) {
30
            // Simple graphs often forbid self-loops; skip or handle as needed
31
            // Here we allow it: it adds 1 on the diagonal
32
            A[u][v] = 1; // For multigraphs, consider incrementing instead of setting
33
        } else {
34
            A[u][v] = 1;
35
            A[v][u] = 1; // ensure symmetry for undirected graphs
36
        }
37
    }
38
39
    // Compute degrees as row sums
40
    vector<long long> deg(n, 0);
41
    for (int i = 0; i < n; ++i) {
42
        long long s = 0;
43
        for (int j = 0; j < n; ++j) s += A[i][j];
44
        deg[i] = s;
45
    }
46
47
    // Build Degree matrix D and Laplacian L = D - A
48
    vector<vector<long long>> D(n, vector<long long>(n, 0));
49
    vector<vector<long long>> L(n, vector<long long>(n, 0));
50
    for (int i = 0; i < n; ++i) {
51
        D[i][i] = deg[i];
52
    }
53
    for (int i = 0; i < n; ++i) {
54
        for (int j = 0; j < n; ++j) {
55
            L[i][j] = (i == j ? D[i][i] : 0) - A[i][j];
56
        }
57
    }
58
59
    // Optional: verify Handshaking Lemma (for undirected without self-loops)
60
    long long sum_deg = 0;
61
    for (int i = 0; i < n; ++i) sum_deg += deg[i];
62
    cerr << "Sum of degrees = " << sum_deg << " (should be 2*m if no self-loops)\n";
63
64
    // Print matrices
65
    cout << "Adjacency matrix A:\n";
66
    for (int i = 0; i < n; ++i) {
67
        for (int j = 0; j < n; ++j) cout << A[i][j] << (j+1==n?'\n':' ');
68
    }
69
70
    cout << "Degree matrix D:\n";
71
    for (int i = 0; i < n; ++i) {
72
        for (int j = 0; j < n; ++j) cout << D[i][j] << (j+1==n?'\n':' ');
73
    }
74
75
    cout << "Laplacian L = D - A:\n";
76
    for (int i = 0; i < n; ++i) {
77
        for (int j = 0; j < n; ++j) cout << L[i][j] << (j+1==n?'\n':' ');
78
    }
79
80
    return 0;
81
}
82

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Input format:
5
// n m\n
6
// m lines: u v (0-based), undirected
7
// s (source vertex)
8
// Output: distance from s to every vertex (−1 if unreachable)
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n, m; if (!(cin >> n >> m)) return 0;
15
    vector<vector<int>> adj(n);
16
    for (int e = 0; e < m; ++e) {
17
        int u, v; cin >> u >> v;
18
        if (u < 0 || u >= n || v < 0 || v >= n) return 0;
19
        adj[u].push_back(v);
20
        adj[v].push_back(u); // undirected
21
    }
22
23
    int s; cin >> s;
24
    if (s < 0 || s >= n) return 0;
25
26
    const int INF = -1;
27
    vector<int> dist(n, INF);
28
    queue<int> q;
29
30
    // Initialize
31
    dist[s] = 0;
32
    q.push(s);
33
34
    while (!q.empty()) {
35
        int u = q.front(); q.pop();
36
        for (int v : adj[u]) {
37
            if (dist[v] == INF) { // not visited yet
38
                dist[v] = dist[u] + 1; // one more edge
39
                q.push(v);
40
            }
41
        }
42
    }
43
44
    // Output distances
45
    for (int i = 0; i < n; ++i) {
46
        cout << dist[i] << (i+1==n?'\n':' ');
47
    }
48
    return 0;
49
}
50

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Input format:
5
// n m\n
6
// m lines: u v (0-based), undirected
7
// s (source)
8
// Output: distance from s to every vertex (−1 if unreachable)
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n, m; if (!(cin >> n >> m)) return 0;
15
    vector<vector<int>> A(n, vector<int>(n, 0));
16
    for (int e = 0; e < m; ++e) {
17
        int u, v; cin >> u >> v;
18
        if (u < 0 || u >= n || v < 0 || v >= n) return 0;
19
        A[u][v] = 1;
20
        A[v][u] = 1; // undirected
21
    }
22
    int s; cin >> s; if (s < 0 || s >= n) return 0;
23
24
    const int INF = -1;
25
    vector<int> dist(n, INF);
26
    queue<int> q;
27
28
    dist[s] = 0; q.push(s);
29
30
    while (!q.empty()) {
31
        int u = q.front(); q.pop();
32
        // Scan entire row u to find neighbors (costly when sparse)
33
        for (int v = 0; v < n; ++v) {
34
            if (A[u][v] && dist[v] == INF) {
35
                dist[v] = dist[u] + 1;
36
                q.push(v);
37
            }
38
        }
39
    }
40
41
    for (int i = 0; i < n; ++i) {
42
        cout << dist[i] << (i+1==n?'\n':' ');
43
    }
44
    return 0;
45
}
46