Posted on 2011-07-28 20:57
Mato_No1 閱讀(1793)
評論(0) 編輯 收藏 引用 所屬分類:
圖算法
在圖DFS的過程中，給每個點(diǎn)設(shè)立兩個附加值dfn和low。dfn[i]表示點(diǎn)i被發(fā)現(xiàn)（變灰）的時間，也就是“發(fā)現(xiàn)次序”。而low[i]表示
i能夠到達(dá)的dfn值最小的i的祖先結(jié)點(diǎn)或i本身的dfn值，即low[i]=min{dfn[i], dfn[j], low[k]}（其中j為滿足以下條件的點(diǎn)：圖中存在邊<i, j>且
這條邊在遍歷到的時候j在棧中（這個棧的具體說明見下）；k為遍歷樹中i的某個子結(jié)點(diǎn)，）。
Tarjan算法就是在圖DFS過程中，得到每個點(diǎn)的dfn值和low值，并且設(shè)立一個棧，點(diǎn)變灰的時候入棧，在某個點(diǎn)i的low值真正確定后（容易發(fā)現(xiàn)，一個點(diǎn)只有變黑了，它的low值才真正確定），若low[i]=dfn[i]，則將棧中點(diǎn)i及其上面的所有點(diǎn)全部彈出（這些點(diǎn)一定是以i為根的子樹中的結(jié)點(diǎn)，因?yàn)樗鼈儽萯后入棧，卻比i先出棧），
這些點(diǎn)組成一個強(qiáng)連通分支，這樣在圖DFS遍歷完后，即可得到所有的強(qiáng)連通分支。
下面證明結(jié)點(diǎn)i變黑時，若low[i]=dfn[i]，則i及其所有未出棧的后代組成一個強(qiáng)連通分支。
證明這個需要分兩步：
【1】i的所有未出棧的后代與i處于同一個強(qiáng)連通分支。設(shè)j是i的某個后代且j在i變黑時尚未出棧。顯然i可達(dá)j，因此只需證明j可達(dá)i。
在遍歷樹中，從i到j(luò)路徑上除i外的所有結(jié)點(diǎn)的low值都小于dfn值（否則，設(shè)這條路徑上存在結(jié)點(diǎn)k，k≠i，low[k]=dfn[k]。因?yàn)閗比i先變黑，所以在k變黑時，其所有后代就會出棧，這與j在i變黑時仍未出棧矛盾，故這樣的結(jié)點(diǎn)k不存在）。設(shè)dfn[x]=low[j]，則根據(jù)low的定義以及l(fā)ow[j]<dfn[j]得，必然是j的祖先且從j先往下再經(jīng)過一條逆向邊可以到達(dá)點(diǎn)x，并且，x不可能是i的祖先（若x是i的祖先，則i先往下再經(jīng)過一條逆向邊可達(dá)x，因此dfn[x]>=low[i]，又因?yàn)閐fn[x]<dfn[i]，所以low[i]<dfn[i]，這與low[i]=dfn[i]矛盾），也就是x位于路徑i->j上且x≠j。若x=i，則j可達(dá)i，結(jié)束，否則先從j到達(dá)x，再將x當(dāng)成j，繼續(xù)往上……這樣最終必然能到達(dá)點(diǎn)i。因此j可達(dá)i，即j與i處于同一個強(qiáng)連通分支。
【2】不是i的未出棧的后代不與i處于同一個強(qiáng)連通分支。
設(shè)j不是i的未出棧的后代，則j有兩種情況：
（1）j是i的后代，且在i變黑前已經(jīng)出棧：
此時，i->j路徑上必然存在一個點(diǎn)k，滿足k≠i，且dfn[k]=low[k]（這樣的k可能有多個，此時取最深的那個為k），當(dāng)k變黑時j出棧。這時，由與【1】類似的推導(dǎo)過程可得，j不斷往上到達(dá)的最上層祖先結(jié)點(diǎn)也只能是k，到不了i，故j不可達(dá)i，也即j與i不處于同一個強(qiáng)連通分支；
（2）j不是i的后代，考慮當(dāng)i變黑時，j的顏色：
<1>白色：此時，若i可達(dá)j，則j在i變黑前，就會成為i的后代，這與j不是i的后代矛盾，故i一定不可達(dá)j，也即j與i不處于同一個強(qiáng)連通分支；
<2>灰色：若j為灰色，則j一定是i的祖先，若i可達(dá)j，根據(jù)low的定義可得，必有l(wèi)ow[i]<=dfn[j]<dfn[i]，這與low[i]=dfn[i]矛盾，故i不可達(dá)j，也即j與i不處于同一個強(qiáng)連通分支；
<3>黑色：若j不是i的后代，且比i先變黑，則必然是在i變灰前j已經(jīng)變黑。這時，若j可達(dá)i，則i會成為j的后代，也即j是i的祖先，這樣在i變黑時，j應(yīng)為灰色，矛盾，故j不可達(dá)i，也即j與i不處于同一個強(qiáng)連通分支；
綜上可得，i、j一定不處于同一個強(qiáng)連通分支。故原命題得證，也就證明了Tarjan算法是可以求出有向圖的所有強(qiáng)連通分支的。
時間復(fù)雜度分析：由于每個點(diǎn)都要入棧一次，出棧一次，每條邊都要被訪問一次，所以總時間復(fù)雜度為O(N+M)。
寫代碼時注意事項：
（1）要用人工棧實(shí)現(xiàn)DFS，不可用遞歸，防止爆棧；另外注意不要將這個人工棧與上面說到的“棧”弄混，本沙茶下面的代碼中，用于搜索、回溯的人工棧為stk0，而用于找強(qiáng)分支的棧為stk；
（2）注意邊界情況；
（3）注意在出棧時要將V值設(shè)為2；
（4）注意計算low[i]時，需要考慮非i的祖先，但仍在棧中的結(jié)點(diǎn)，它們也被視為i的“祖先”。
核心代碼：
void solve()
{
re(i, n) {V[i] = vst[i] = 0; st[i] = E[i].next;}
int x, y, x0, tp, tp0, ord = 0, No = 0;
bool fd;
re(i, n) if (!V[i]) {
stk[tp = 0] = stk0[tp0 = 0] = i; vst[i] = 1; low[i] = dfn[i] = ++ord; V[i] = 1;
while (tp0 >= 0) {
x = stk0[tp0]; fd = 0;
for (int p=st[x]; p != x; p=E[p].next) {
y = E[p].b;
if (!V[y]) {
fd = 1; stk[++tp] = stk0[++tp0] = y; vst[y] = 1; low[y] = dfn[y] = ++ord; V[y] = 1; st[x] = E[p].next; break;
} else if (vst[y] && dfn[y] < low[x]) low[x] = dfn[y];
}
if (!fd) {
V[x] = 2;
if (low[x] == dfn[x]) {while (stk[tp] != x) {vst[stk[tp]] = 0; w[stk[tp--]] = No;} vst[x] = 0; w[stk[tp--]] = No++;}
if (tp0) {x0 = stk0[tp0 - 1]; if (low[x] < low[x0]) low[x0] = low[x];} tp0--;
}
}
}
re(i, n) {reslen[i] = 0; for (int p=E[i].next; p != i; p=E[p].next) if (w[i] == w[E[p].b]) reslen[i]++;}
}