Rare
0/12

# BCCs and 2CCs

Authors: Benjamin Qi, Mihnea Brebenel

## 2-Edge-Connected Components

StatusSourceProblem NameDifficultyTags
YSEasy
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.

Any help would be appreciated! Just submit a Pull Request on Github.

(implementation)

### With DSU

StatusSourceProblem NameDifficultyTags
PlatNormal
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.

Any help would be appreciated! Just submit a Pull Request on Github.

(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] = x			x = 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;

### 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

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsBCC
POINormal
Show TagsBCC
APIONormal
Show TagsBCC
POINormal
Show TagsBCC
TLEHard
Show TagsBCC
CEOIHard
Show TagsBCC
PlatVery Hard
Show TagsBCC

### 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!