Bridges and Articulation Points

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes bridges and articulation points in an undirected graph using DFS.
5
// - 0-indexed vertices [0..n-1]
6
// - Handles disconnected graphs
7
// - Works with parallel edges; the non-parent parallel edge serves as a back edge
8
9
struct Graph {
10
    int n;
11
    vector<vector<int>> adj; // adjacency list
12
    Graph(int n) : n(n), adj(n) {}
13
    void add_edge(int u, int v) {
14
        adj[u].push_back(v);
15
        adj[v].push_back(u);
16
    }
17
};
18
19
struct BridgesAP {
20
    int n;
21
    const vector<vector<int>> &adj;
22
    vector<int> disc, low, parent;
23
    vector<bool> is_art;
24
    vector<pair<int,int>> bridges;
25
    int timer;
26
27
    BridgesAP(const Graph &g)
28
        : n(g.n), adj(g.adj), disc(n, -1), low(n, -1), parent(n, -1), is_art(n, false), timer(0) {}
29
30
    void dfs(int u) {
31
        disc[u] = low[u] = timer++; // set discovery time and initial low
32
        int child_count = 0;        // number of DFS children of u
33
34
        for (int v : adj[u]) {
35
            if (v == parent[u]) {
36
                // Skip the exact parent edge in undirected graphs
37
                continue;
38
            }
39
            if (disc[v] == -1) {
40
                // Tree edge u -> v
41
                parent[v] = u;
42
                child_count++;
43
                dfs(v);
44
                // After recursion, update low[u] using child's low
45
                low[u] = min(low[u], low[v]);
46
47
                // Bridge test: If v's subtree cannot reach u or above
48
                if (low[v] > disc[u]) {
49
                    bridges.emplace_back(min(u, v), max(u, v));
50
                }
51
                // Articulation test for non-root u
52
                if (parent[u] != -1 && low[v] >= disc[u]) {
53
                    is_art[u] = true;
54
                }
55
            } else {
56
                // Back edge u -> v to an ancestor (disc[v] < disc[u])
57
                // Use discovery times to detect ancestor; in undirected graphs
58
                // a forward edge to a discovered descendant shouldn't appear here
59
                low[u] = min(low[u], disc[v]);
60
            }
61
        }
62
        // Special rule for root: articulation iff it has >= 2 DFS children
63
        if (parent[u] == -1 && child_count >= 2) {
64
            is_art[u] = true;
65
        }
66
    }
67
68
    void run() {
69
        for (int u = 0; u < n; ++u) {
70
            if (disc[u] == -1) dfs(u);
71
        }
72
        sort(bridges.begin(), bridges.end());
73
        bridges.erase(unique(bridges.begin(), bridges.end()), bridges.end());
74
    }
75
};
76
77
int main() {
78
    ios::sync_with_stdio(false);
79
    cin.tie(nullptr);
80
81
    // Example usage:
82
    // Input format:
83
    // n m
84
    // m lines of edges u v (0-indexed)
85
86
    int n, m;
87
    if (!(cin >> n >> m)) return 0;
88
    Graph g(n);
89
    for (int i = 0; i < m; ++i) {
90
        int u, v; cin >> u >> v; g.add_edge(u, v);
91
    }
92
93
    BridgesAP solver(g);
94
    solver.run();
95
96
    // Output articulation points
97
    cout << "Articulation Points:\n";
98
    for (int u = 0; u < n; ++u) if (solver.is_art[u]) cout << u << " ";
99
    cout << "\n";
100
101
    // Output bridges
102
    cout << "Bridges:\n";
103
    for (auto [u, v] : solver.bridges) cout << u << " " << v << "\n";
104
105
    return 0;
106
}
107

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Build 2-edge-connected components by first finding bridges, then contracting
5
// non-bridge edges. The resulting bridge tree is a forest (a tree per component).
6
// Useful for path queries where only bridges matter.
7
8
struct Edge { int u, v; };
9
10
struct Graph {
11
    int n; vector<vector<pair<int,int>>> adj; // (to, edge_id)
12
    vector<Edge> edges;
13
    Graph(int n): n(n), adj(n) {}
14
    int add_edge(int u, int v){
15
        int id = (int)edges.size();
16
        edges.push_back({u,v});
17
        adj[u].push_back({v,id});
18
        adj[v].push_back({u,id});
19
        return id;
20
    }
21
};
22
23
struct Bridges {
24
    int n; const Graph &g; int timer;
25
    vector<int> disc, low, peid; // peid: parent edge id
26
    vector<char> is_bridge; // mark bridges by edge id
27
    Bridges(const Graph &g): n(g.n), g(g), timer(0), disc(n,-1), low(n,-1), peid(n,-1), is_bridge(g.edges.size(), 0) {}
28
29
    void dfs(int u){
30
        disc[u] = low[u] = timer++;
31
        for (auto [v, id] : g.adj[u]){
32
            if (id == peid[u]) continue; // skip parent edge
33
            if (disc[v] == -1){
34
                peid[v] = id;
35
                dfs(v);
36
                low[u] = min(low[u], low[v]);
37
                if (low[v] > disc[u]) is_bridge[id] = 1;
38
            } else {
39
                // back edge to ancestor (disc[v] < disc[u])
40
                low[u] = min(low[u], disc[v]);
41
            }
42
        }
43
    }
44
45
    void run(){
46
        for (int u = 0; u < n; ++u) if (disc[u] == -1) dfs(u);
47
    }
48
};
49
50
// After marking bridges, assign component ids by DFS that ignores bridges
51
struct BridgeTreeBuilder {
52
    const Graph &g; Bridges &br;
53
    vector<int> comp; // component id per vertex
54
    int comps;
55
56
    BridgeTreeBuilder(const Graph &g, Bridges &br): g(g), br(br), comp(g.n, -1), comps(0) {}
57
58
    void dfs_comp(int u, int cid){
59
        comp[u] = cid;
60
        for (auto [v, id] : g.adj[u]){
61
            if (comp[v] != -1) continue;
62
            if (br.is_bridge[id]) continue; // don't cross bridges
63
            dfs_comp(v, cid);
64
        }
65
    }
66
67
    vector<vector<int>> build_tree(){
68
        // Assign component ids
69
        for (int u = 0; u < g.n; ++u) if (comp[u] == -1) dfs_comp(u, comps++);
70
        // Tree has 'comps' nodes. Add edges for each bridge.
71
        vector<vector<int>> tree(comps);
72
        for (int id = 0; id < (int)g.edges.size(); ++id){
73
            if (!br.is_bridge[id]) continue;
74
            int u = g.edges[id].u;
75
            int v = g.edges[id].v;
76
            int a = comp[u], b = comp[v];
77
            if (a == b) continue; // should not happen for a bridge
78
            tree[a].push_back(b);
79
            tree[b].push_back(a);
80
        }
81
        return tree;
82
    }
83
};
84
85
int main(){
86
    ios::sync_with_stdio(false);
87
    cin.tie(nullptr);
88
89
    int n, m; if (!(cin >> n >> m)) return 0;
90
    Graph g(n);
91
    for (int i = 0; i < m; ++i){ int u,v; cin >> u >> v; g.add_edge(u,v); }
92
93
    Bridges br(g); br.run();
94
    BridgeTreeBuilder builder(g, br);
95
    auto tree = builder.build_tree();
96
97
    // Output components and tree
98
    cout << "Components (2-edge-connected):\n";
99
    for (int u = 0; u < n; ++u) cout << u << ": " << builder.comp[u] << '\n';
100
101
    cout << "Bridge Tree adjacency:\n";
102
    for (int i = 0; i < (int)tree.size(); ++i){
103
        cout << i << ":";
104
        for (int v : tree[i]) cout << ' ' << v;
105
        cout << '\n';
106
    }
107
    return 0;
108
}
109

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Build the block-cut tree: articulation points (original vertex nodes) connected to
5
// biconnected component nodes. The final tree is bipartite: [0..n-1] for original
6
// vertices and [n..n+bcc_cnt-1] for block nodes.
7
8
struct Graph {
9
    int n; vector<vector<int>> adj;
10
    Graph(int n): n(n), adj(n) {}
11
    void add_edge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u); }
12
};
13
14
struct BlockCutTree {
15
    const Graph &g; int n;
16
    vector<int> disc, low, parent;
17
    int timer = 0;
18
    vector<pair<int,int>> st; // stack of edges in current DFS path
19
    vector<vector<int>> bcc;  // list of biconnected components as vertex lists
20
    vector<char> is_art;
21
22
    BlockCutTree(const Graph &g): g(g), n(g.n), disc(n,-1), low(n,-1), parent(n,-1), is_art(n,0) {}
23
24
    void pop_component(int u, int v){
25
        // Pop edges until (u,v) is popped; collect unique vertices in this block
26
        vector<int> verts;
27
        unordered_set<int> seen;
28
        while (!st.empty()){
29
            auto [a,b] = st.back(); st.pop_back();
30
            if (!seen.count(a)) { seen.insert(a); verts.push_back(a); }
31
            if (!seen.count(b)) { seen.insert(b); verts.push_back(b); }
32
            if ((a==u && b==v) || (a==v && b==u)) break;
33
        }
34
        bcc.push_back(move(verts));
35
    }
36
37
    void dfs(int u){
38
        disc[u] = low[u] = timer++;
39
        int child_count = 0;
40
        for (int v : g.adj[u]){
41
            if (v == parent[u]) continue;
42
            if (disc[v] == -1){
43
                parent[v] = u;
44
                child_count++;
45
                st.emplace_back(u, v);
46
                dfs(v);
47
                low[u] = min(low[u], low[v]);
48
                // If v's subtree cannot reach u's ancestors, we found a block
49
                if (low[v] >= disc[u]){
50
                    if (parent[u] != -1) is_art[u] = 1; // non-root AP rule
51
                    pop_component(u, v);
52
                }
53
            } else if (disc[v] < disc[u]){
54
                // back edge to ancestor only (avoid pushing descendant -> ancestor twice)
55
                st.emplace_back(u, v);
56
                low[u] = min(low[u], disc[v]);
57
            }
58
        }
59
        if (parent[u] == -1 && child_count >= 2) is_art[u] = 1; // root AP rule
60
    }
61
62
    // Returns: block-cut tree adjacency, size = n + bcc_cnt
63
    vector<vector<int>> build(){
64
        for (int u = 0; u < n; ++u) if (disc[u] == -1) dfs(u);
65
        int bcc_cnt = (int)bcc.size();
66
        vector<vector<int>> BCT(n + bcc_cnt);
67
        for (int i = 0; i < bcc_cnt; ++i){
68
            int block_node = n + i; // block node index
69
            for (int v : bcc[i]){
70
                // connect original vertex v to block node
71
                BCT[v].push_back(block_node);
72
                BCT[block_node].push_back(v);
73
            }
74
        }
75
        return BCT;
76
    }
77
};
78
79
int main(){
80
    ios::sync_with_stdio(false);
81
    cin.tie(nullptr);
82
83
    int n, m; if (!(cin >> n >> m)) return 0;
84
    Graph g(n);
85
    for (int i = 0; i < m; ++i){ int u,v; cin >> u >> v; g.add_edge(u,v); }
86
87
    BlockCutTree solver(g);
88
    auto BCT = solver.build();
89
90
    cout << "Articulation Points:\n";
91
    for (int u = 0; u < n; ++u) if (solver.is_art[u]) cout << u << ' ';
92
    cout << '\n';
93
94
    cout << "Biconnected Components (as vertex lists):\n";
95
    for (int i = 0; i < (int)solver.bcc.size(); ++i){
96
        cout << "Block " << i << ":";
97
        for (int v : solver.bcc[i]) cout << ' ' << v;
98
        cout << '\n';
99
    }
100
101
    cout << "Block-Cut Tree adjacency (0.." << (int)BCT.size()-1 << "):\n";
102
    for (int i = 0; i < (int)BCT.size(); ++i){
103
        cout << i << ":";
104
        for (int v : BCT[i]) cout << ' ' << v;
105
        cout << '\n';
106
    }
107
    return 0;
108
}
109