誤読

文字通りくそコード

Tarjan's SCC

lowlinkを書いたばかりだったので、lowlinkを使ってSCCが書けると聞いて飛びついた。(が、完全に罠だった)

kosarajuは書いたことあるけどtarjanはないって人多そう(実際のとこ定数倍とかで早いのはどっち)

日本語の資料が微塵もなくて辛かった(有志は英wiki全部移植して)

①強連結成分は、dfs木を作ったときに必ず部分木になる(強連結成分はどの点からでもすべての点に行けるのでそれはそう)

②lowlinkとorderが等しい頂点が強連結成分の部分木の根(もしlowlinkのほうが小さかったら、それよか上まで自由に行けるので)

ので、dfsの行きがけでスタックに頂点を積んでいき、戻るときにlowlinkとorderが等しい頂点が見つかったら現在いる頂点が出てくるまでスタックから積んできた頂点を取り出す。そいつらがひとまとまりの強連結成分。

f:id:akihiro1001:20170327113005j:plain:w300

・罠

一般的なlowlinkは無向グラフでやるもので、有向グラフでlowlinkを無向と同様にやるとdfsするときの順番で結果が変わってしまうので少し違う。無向の時は後退辺だけだが、有向の場合は再帰のスタックに積まれてる頂点への辺も含めて考える。(ほんとにどこにも書いてなくて有向リンク界隈の廃れを感じる(そんなものはない))

あと、これを使って2-SATを書いたよ

void SCC(DGraph& g, vector<int>& scc) {
	vector<int>  orb(g.vn, -1);
	scc.resize(g.vn, -1);
	int cc = 0,k = 0;

	vector<bool> used(g.vn);
	stack<int> st;
	function<int(int)> dfs = [&](int cur) {
		int low = orb[cur] = ++k;
		st.push(cur);
		used[cur] = 1;
		for (auto itr : g.g[cur]) {
			if (orb[itr.first] == -1)
				low = min(low, dfs(itr.first));
			else if (used[itr.first])
				low = min(low, orb[itr.first]);
		}
		if (low == orb[cur]) {
			while (1) {
				int cp = st.top(); st.pop();
				used[cp] = 0;
				scc[cp] = cc;
				if (cp == cur)
					break;
			}
			cc++;
		}
		return low;
	};
	REP(i, g.vn)
		if (orb[i] < 0)
			dfs(i);
}