BCCs and 2CCs

2-Edge-Connected Components

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

note that BCCs contain EDGES not VERTICES

Related topics include

• Articulation Points
• Bridges
• Block-Cut Tree

Tutorial

(implementation)

Problems