### humblefOOOol's blog

By humblefOOOol, history, 4 weeks ago, After constructing bridge tree, we have bi-connected components as nodes and bridges as edges. Is there any possible way to print every bicomponent which is a node in bridge tree.

eg: Its bridge tree is Can we print all biconnected components from bridge tree itself?

Here in the above graph : Comp1 -> (1-2-3-4) Comp2--> (5-6-7) Comp3-->(5-9) Comp4---> (7-8) Comments (8)
 » Auto comment: topic has been updated by humblefOOOol (previous revision, new revision, compare).
 » Can any one help in this problem. Its from cf blog https://codeforces.com/blog/entry/83980#:~:text=2%2Dedge%20connected%20component%20in,have%20any%20bridges%20in%20it.
 » Not exactly sure what your question is, do you mean recover Comp1 -> (1-2-3-4) Comp2--> (5-6-7) Comp3-->(5-9) Comp4---> (7-8) from just looking at the graph? The IDs 1, 2, 3, 4 are just arbitrary numbers representing the components, there's no special connection between the number 1 and the set [1, 2, 3, 4]. If you mean recovering the original nodes after building the bridge tree, you could just store them in a 2D vector when building.
•  » » Yes I am maintaining a 2 -d vector but in this example I am not able to retrieve all components My sample codeconst int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5;int N, M, timer, compid;vector> g[MAXN]; bool used[MAXN], isBridge[MAXM]; int comp[MAXN], tin[MAXN], minAncestor[MAXN];vector tree[MAXN]; // Store 2-edge-connected component tree.(Bridge tree).void dfs(int v, int p) { tin[v] = minAncestor[v] = ++timer; used[v] = 1; for(auto &e: g[v]) { int to, id; tie(to, id) = e; if(to == p) continue; if(used[to]) { minAncestor[v] = min(minAncestor[v], tin[to]); } else { dfs(to, v); minAncestor[v] = min(minAncestor[v], minAncestor[to]); if(minAncestor[to] > tin[v]) { isBridge[id] = true; } } } }void dfs1(int v, int p) { used[v] = 1; comp[v] = compid; for(auto &e: g[v]) { int to, id; tie(to, id) = e; if(isBridge[id]) { // avoid traversing from this edge. so we get full component. continue; } if(used[to]) { continue; } dfs1(to, v); }}vector> edges;void addEdge(int from, int to, int id) { g[from].push_back({to, id}); g[to].push_back({from, id}); edges[id] = {from, to}; }void initB() { for(int i = 0; i <= compid; ++i) tree[i].clear(); for(int i = 1; i <= N; ++i) used[i] = false; for(int i = 1; i <= M; ++i) isBridge[i] = false; timer = 0; compid = 0;}void bridge_tree() { initB(); dfs(1, -1); //Assuming graph is connected. for(int i = 1; i <= N; ++i) used[i] = 0; for(int i = 1; i <= N; ++i) { if(!used[i]) { dfs1(i, -1); ++compid; } } for(int i = 1; i <= M; ++i) { if(isBridge[i]) { int u, v; tie(u, v) = edges[i]; // connect two componets using edge. tree[comp[u]].push_back(comp[v]); tree[comp[v]].push_back(comp[u]); } }}void init() { edges.clear(); edges.resize(M + 1); for(int i = 1; i <= N; ++i) g[i].clear(); }void solve() { cin >> N >> M; init(); for(int i = 1; i <= M; ++i) { int u, v; cin >> u >> v; addEdge(u, v, i); } bridge_tree();}
•  » » » Here when i am creating a tree when i am trying to retrieve those components its not working
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   In your DFS method, you can maintain a stack holding all the nodes you visit, then whenever you encounter a bridge, continuously pop nodes off the stack until you pop off an endpoint of the bridge, and all nodes you just popped off will form a component in the bridge tree. It's easier to just show code: Click Me// low and num are dfs numbers as defined in the canonical algorithm explained by most tutorials // comp is the 2D vector storing all the nodes // id labels which component the node belongs in int dfs(int u, int p) { int low = num[u] = ++ti; stk.push_back(u); for (int v : adj[u]) if (v != p) { if (!num[v]) { int ret = dfs(v, u); low = min(low, ret); if (num[u] < ret) { // the edge (u, v) is a bridge comp.emplace_back(); do { id[stk.back()] = (int) comp.size() - 1; comp.back().push_back(stk.back()); stk.pop_back(); } while (comp.back().back() != v); // everything just popped off belongs to one component } } else { low = min(low, num[v]); } } return low; } If at the end of the DFS your stack isn't empty, then all remaining nodes in the stack form the last component.
•  » » » » » Thank you so much. It absolutely worked. What if we create a block-cut tree. is it the same to retrieve the bcc from there too?
•  » » » » » » Yea, just pop from the stack at each articulation point instead of bridge.