強連通まとめ

定義:1つの有向図では、1つの図をいくつかの分岐に分けることができ、各分岐の任意の2つのノードが互いに達するように経路を持っている場合、この分岐を強連通分岐と呼ぶ.
次に,強い連通分岐を求める方向図を与え,Tarjan発明のアルゴリズムを利用することができる.
強連通分岐を求めると,問題に基づいて,各強連通分岐を縮点することができ,縮点後の図は有向無ループ図(DAG)になり,DP,最短回路,最小生成ツリーなどのアルゴリズムを行うことができる.
テンプレート:

const int N = 505;

int n;
vector<Edge> g[N];

int pre[N], dfn[N], dfs_clock, sccn, sccno[N];
stack<int> S;

void dfs_scc(int u) {
	pre[u] = dfn[u] = ++dfs_clock;
	S.push(u);
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].v;
		if (!pre[v]) {
			dfs_scc(v);
			dfn[u] = min(dfn[u], dfn[v]);
		} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);
	}
	if (pre[u] == dfn[u]) {
		sccn++;
		while (1) {
			int x = S.top(); S.pop();
			sccno[x] = sccn;
			if (x == u) break;
		}
	}
}

void find_scc() {
	dfs_clock = sccn = 0;
	memset(sccno, 0, sizeof(sccno));
	memset(pre, 0, sizeof(pre));
	for (int i = 1; i <= n; i++)
		if (!pre[i]) dfs_scc(i);
}

タイトル:

強連通の裸問題:

1、強い連通図であるか否かを直接判断し、また、いずれも1つの連通ブロック内にあるか否かに注意しなければならない.
HDU 1269迷宮城この問題はテンプレート1類POJ 3180 The Cow Promが強い連通成分の中の元素の個数が1より大きい個数2類を探すために使用することができる.

入度出度に関する強い連通:

1、いくつかの辺をプラスして図強を連通させる:まず点を縮めて、それから縮めた図入度が0と出度が0の点の個数を計算して、大きいのは必然的に答えで、最初から強く連通すれば、0を出力する2、どの点から(あるいはいくつかの点を置く)、すべての点が着くように注意しなければならない
縮めるとすべての入度が0になる点が置かれる位置であるHDU 2767 Proving Equivalences 1類HDU 3836 Equivalent Sets 1類HDU 1827 Summer Holiday 2類POJ 1236 Network of Schools 1+2類POJ 2553 The Bottom of a Graphこの問題は度が0の強い連通分岐POJ 2186 Popular Cowsを探し出すいくつかの点が別の点で到達可能であることに注意して度が0の点が1より大きいと判断した場合、答えは0 POJ 2375 Cow Ski Areaが題意に基づいてモデリングした後に1種類の問題であるべきだ.

圧縮点を強く接続した後、他の知識を結合します。

一般的にいくつかの問題は、有向無環図で解決できる場合、図が有環になる可能性がある場合は、縮点を考慮し、縮点後の点権は問題によって決まり、残りは縮点後の図で、別の問題を解決します.
HDU 3072 Intelligence System縮点の後に最小ツリー図HDU 3861 The King’s Problem縮点の後に最小パスを走ってHDU 3639 Hawk-and-Chicken縮点の後にDP POJ 2762 Going from u to v or from v to u?縮点後のトポロジーソートは、分岐POJ 3160 Father Christmas flymouse縮点後DP(dag上の最長経路)POJ 3114 Countries in War縮点後最短経路POJ 3592 Instantaneous Transferenceが題意に従ってモデリングされ、縮点後DPが出現しないと判断する

特殊:

有向サボテン図判定:HDU 3594 Cactusは強連通分岐を探す過程において、リングが出現した場合、経路上の点値をすべて+1し、ある時点である点値が2であれば、満足しないに違いない、そして一つの連通ブロック内にあるかどうかを判断すればよい
POJ 1904 King's Questは二分図マッチングの知識を結合し,問題を強連通に変換して解決した.