Posted on 2011-07-28 20:57
Mato_No1 阅读(1761)
评论(0) 编辑 收藏 引用 所属分类:
图算法
在图DFS的过程中，给每个点设立两个附加值dfn和low。dfn[i]表示点i被发现（变灰）的时间，也就是“发现次序”。而low[i]表示
i能够到达的dfn值最小的i的祖先结点或i本身的dfn值，即low[i]=min{dfn[i], dfn[j], low[k]}（其中j为满足以下条件的点：图中存在边<i, j>且
这条边在遍历到的时候j在栈中（这个栈的具体说明见下）；k为遍历树中i的某个子结点，）。
Tarjan算法就是在图DFS过程中，得到每个点的dfn值和low值，并且设立一个栈，点变灰的时候入栈，在某个点i的low值真正确定后（容易发现，一个点只有变黑了，它的low值才真正确定），若low[i]=dfn[i]，则将栈中点i及其上面的所有点全部弹出（这些点一定是以i为根的子树中的结点，因为它们比i后入栈，却比i先出栈），
这些点组成一个强连通分支，这样在图DFS遍历完后，即可得到所有的强连通分支。
下面证明结点i变黑时，若low[i]=dfn[i]，则i及其所有未出栈的后代组成一个强连通分支。
证明这个需要分两步：
【1】i的所有未出栈的后代与i处于同一个强连通分支。设j是i的某个后代且j在i变黑时尚未出栈。显然i可达j，因此只需证明j可达i。
在遍历树中，从i到j路径上除i外的所有结点的low值都小于dfn值（否则，设这条路径上存在结点k，k≠i，low[k]=dfn[k]。因为k比i先变黑，所以在k变黑时，其所有后代就会出栈，这与j在i变黑时仍未出栈矛盾，故这样的结点k不存在）。设dfn[x]=low[j]，则根据low的定义以及low[j]<dfn[j]得，必然是j的祖先且从j先往下再经过一条逆向边可以到达点x，并且，x不可能是i的祖先（若x是i的祖先，则i先往下再经过一条逆向边可达x，因此dfn[x]>=low[i]，又因为dfn[x]<dfn[i]，所以low[i]<dfn[i]，这与low[i]=dfn[i]矛盾），也就是x位于路径i->j上且x≠j。若x=i，则j可达i，结束，否则先从j到达x，再将x当成j，继续往上……这样最终必然能到达点i。因此j可达i，即j与i处于同一个强连通分支。
【2】不是i的未出栈的后代不与i处于同一个强连通分支。
设j不是i的未出栈的后代，则j有两种情况：
（1）j是i的后代，且在i变黑前已经出栈：
此时，i->j路径上必然存在一个点k，满足k≠i，且dfn[k]=low[k]（这样的k可能有多个，此时取最深的那个为k），当k变黑时j出栈。这时，由与【1】类似的推导过程可得，j不断往上到达的最上层祖先结点也只能是k，到不了i，故j不可达i，也即j与i不处于同一个强连通分支；
（2）j不是i的后代，考虑当i变黑时，j的颜色：
<1>白色：此时，若i可达j，则j在i变黑前，就会成为i的后代，这与j不是i的后代矛盾，故i一定不可达j，也即j与i不处于同一个强连通分支；
<2>灰色：若j为灰色，则j一定是i的祖先，若i可达j，根据low的定义可得，必有low[i]<=dfn[j]<dfn[i]，这与low[i]=dfn[i]矛盾，故i不可达j，也即j与i不处于同一个强连通分支；
<3>黑色：若j不是i的后代，且比i先变黑，则必然是在i变灰前j已经变黑。这时，若j可达i，则i会成为j的后代，也即j是i的祖先，这样在i变黑时，j应为灰色，矛盾，故j不可达i，也即j与i不处于同一个强连通分支；
综上可得，i、j一定不处于同一个强连通分支。故原命题得证，也就证明了Tarjan算法是可以求出有向图的所有强连通分支的。
时间复杂度分析：由于每个点都要入栈一次，出栈一次，每条边都要被访问一次，所以总时间复杂度为O(N+M)。
写代码时注意事项：
（1）要用人工栈实现DFS，不可用递归，防止爆栈；另外注意不要将这个人工栈与上面说到的“栈”弄混，本沙茶下面的代码中，用于搜索、回溯的人工栈为stk0，而用于找强分支的栈为stk；
（2）注意边界情况；
（3）注意在出栈时要将V值设为2；
（4）注意计算low[i]时，需要考虑非i的祖先，但仍在栈中的结点，它们也被视为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]++;}
}