# BCCs and 2CCs

Authors: Benjamin Qi, Mihnea Brebenel

Resources | ||||
---|---|---|---|---|

CF | ||||

CP2 |

## 2-Edge-Connected Components

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

YS | Easy | ## Show Tags2CC |

C++

#include <bits/stdc++.h>using namespace std;const int MAX_N = 3e5;int timer; // Time of entry in nodeint scc; // Number of strongly connected componentsint id[MAX_N];int low[MAX_N]; // Lowest ID in node's subtree in DFS treevector<int> neighbors[MAX_N];

### This section is not complete.

(implementation)

### With DSU

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Platinum | Normal | ## Show TagsMerging |

The analysis for the above problem mentions an $\mathcal{O}(m\alpha(n))$ solution. Although this is not a two-connected component problem, we can in fact use DSU to generate two-connected components.

### This section is not complete.

(explanation?)

The DSU operations take $\mathcal{O}(\log n)$ rather than $\mathcal{O}(\alpha(n))$ because the DSU does not use union by size, but it's easy to change this.

struct TwoEdgeCC {struct {vi e;void init(int n) { e = vi(n, -1); }int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }bool unite(int x, int y) { // set par[y] = xx = get(x), y = get(y);if (x == y) return 0;e[x] += e[y];e[y] = x;

### Problems

Focus Problem – try your best to solve this problem before continuing!

- SRM 787 1000

## Biconnected Components

Focus Problem – try your best to solve this problem before continuing!

An important observation is that if you can't go from node $a$ to node $b$ without passing through node $c$, node $c$ is a critical node (articulation point). Node $c$ can split $a$ and $b$ into 2 different components if removed. This makes us think about biconnected components.

Now we're left with two cases. If node $c$ isn't critical, a path from $a$ to $b$ can avoid the node. Otherwise, if node $c$ is a critical one we have to check if is on path from $a$ to $b$. Here is a little tricky, on a simple graph, it's not so easy to check, on the other hand, checking this on a tree can be much easier. In order to do this, we transform the graph into a block-cut tree.

In a block-cut tree, every articulation and biconnected component represents a node. Now that we have turned our graph into a tree how do we check if node the path from $a$ to $b$ passes through $c$? To do this we use LCA. You can find more about this here.

C++

#include <bits/stdc++.h>using namespace std;/** @return the block-cut tree of a graph */vector<vector<int>> biconnected_components(vector<vector<int>> &g,vector<bool> &is_cutpoint, vector<int> &id) {int n = (int)g.size();vector<vector<int>> comps;vector<int> stk;

### Articulation Points

Focus Problem – try your best to solve this problem before continuing!

Resources | ||||
---|---|---|---|---|

CP2 | maybe not completely correct |

C++

#include <bits/stdc++.h>using namespace std;const int NMAX = 2e4;int timer;vector<int> low, id;vector<bool> visited, ap;vector<vector<int>> g(NMAX);

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsBCC | |||

POI | Normal | ## Show TagsBCC | |||

APIO | Normal | ## Show TagsBCC | |||

POI | Normal | ## Show TagsBCC | |||

TLE | Hard | ## Show TagsBCC | |||

CEOI | Hard | ## Show TagsBCC | |||

Platinum | Very Hard | ## Show TagsBCC |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!