BCCs and 2CCs

2-Edge-Connected Components

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 3e5;

int timer;  // Time of entry in node
int scc;    // Number of strongly connected components
int id[MAX_N];
int low[MAX_N];  // Lowest ID in node's subtree in DFS tree
vector<int> neighbors[MAX_N];

With DSU

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.

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.

Copy
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

• SRM 787 1000

Biconnected Components

Explanation

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.

Implementation

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

Implementation

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