二辺連結成分分解

目的

任意のある一辺を取り除いても連結である頂点集合への分解を二辺連結成分分解といいます。頂点数$V$、辺数$E$のグラフの二辺連結成分分解を行います。

計算量

$O(V+E)$

使い方

ArrayList<Integer>[] g
頂点i,j間に辺が存在するとき、g[i]にj、g[j]にiを格納してください。
int two_edge_connected_componets(ArrayList<Integer>[] g, int[] col)
int[] colには長さVの空の配列を渡してください。頂点iと頂点jが二辺連結成分分解後、同一集合に含まれるとき、col[i]==col[j]となります。二重辺連結成分分解後の集合の数をreturnします。

ソースコード

int two_edge_connected_componets(ArrayList<Integer>[] g, int[] col) {
	int n = g.length;
	Arrays.fill(col, -1);
	int cols = 0;
	int[] low = new int[n];
	int[] ord = new int[n];
	boolean[] marked = new boolean[n];
	Arrays.fill(low, -1);
	Arrays.fill(ord, -1);
	int order = 0;
	ArrayDeque<State> stk = new ArrayDeque<>();
	ArrayDeque<Integer> pnd = new ArrayDeque<>();
	for (int ii = 0; ii < n; ++ii) {
		if (ord[ii] == -1) {
			stk.add(new State(ii, -1, 0));
		}
		while (!stk.isEmpty()) {
			State s = stk.pollFirst();
			if (ord[s.i] == -1) {
				low[s.i] = (ord[s.i] = order++);
				pnd.addFirst(s.i);
			}
			if (s.j > 0 && s.parent != g[s.i].get(s.j - 1) && !marked[g[s.i].get(s.j - 1)]) {
				low[s.i] = Math.min(low[s.i], low[g[s.i].get(s.j - 1)]);
			}
			if (s.j == g[s.i].size() && low[s.i] == ord[s.i]) {
				while (true) {
					int v = pnd.pollFirst();
					col[v] = cols;
					marked[v] = true;
					if (v == s.i)
						break;
				}
				++cols;
			}
			if (s.j == g[s.i].size())
				continue;
			int v = g[s.i].get(s.j);
			stk.addFirst(new State(s.i, s.parent, s.j + 1));
			if (ord[v] == -1) {
				stk.addFirst(new State(v, s.i, 0));
			} else  if (v != s.parent && !marked[v]) {
				low[s.i] = Math.min(low[s.i], low[v]);
			}
		}
	}
	return cols;
}