有向图的强连通分量

来源：《算法训练营》

ins[u]：记录结点u是否在栈中

注释

tarjan(v);

low[u]=min(low[u], low[v]); // 判断有环。逆向思维：判断有环的方法是对于dfs到达的这个结点继续进行dfs，如果能够回到起点则表示有环。所以在比较low[u]和low[v]之前，需要进行递归dfs。

2. 以tarjan(2)为例

tarjan(2)

dfn_2=low_2=2

ins_2=true

s.push(2)

for() // 因为没有邻接点，所以整个循环都被跳过

if(low_2==dfn_2) //tarjan(2)第一步就是dfn_2=low_2=2

思考：如果2处又有一个强连通分量，程序会怎样运行？

如图，2处有一个强连通分量

标注出dfn和low之后如图。

故在到达强连通分量的起点同时也是终点的2之前，弹出栈顶元素，最后弹出强连通分量7 - 6 - 2，并且退回前一个强连通分量1处。

3. 以tarjan(5)为例

5的邻接点1的dfn已经有解，则表示有环。

在代码中体现为if(!dfn[v])被跳过

5的邻接点1已经在栈中，则表示形成强连通分量。

在代码中体现为else if(ins[v])被执行

注，强连通分量不唯一，这里只是把图划分成了两部分，可以说是求出了极大强连通分量了

思考：如果要求图的所有强连通分量，该如何修改代码？

4. low的赋值历程

① 首先是dfs_u=low_u=u

② 然后是如果有邻接点

③ 如果邻接点没有被dfs过，则dfs。如果有连接到u之前更早的祖先的环，则low_u=low_v=该更早祖先的序号

④ 如果邻接点被dfs过且在栈中，则如果邻接点是u的祖先结点，则low_u=dfn_v=该更早祖先的序号

注意，为什么此处不能low_u=low_v？因为其实此时low_v是一个待定的值，

例如，此时图上有两个强连通分量

两个强连通分量有重边1 － 6，则尽管先dfs了右边的强连通分量，但会先输出左边的强连通分量1－6－7，因为此时low_1还没有被修改，还是次初始状态的low_1=dfn_1=1（原始初始状态是dfn_1=0，这样0才能递归到1），所以满足了输出栈的条件。

但问题是这时1被弹出了，那么右边的强连通分量？？？

本来是low_1在回溯时被修改成low_1=0，然后输出强连通分量4－3－2－6－1－0

代码和运行结果

#include 

#define maxe 100

using namespace std;
int cnt=0;
int num=0;
stack<int>s;

struct node{
    int to, next, w;
}edge[maxe];
int head[maxe];
int low[maxe];
int dfn[maxe];
bool ins[maxe];

void init() {
    for(int i=0; i)
        head[i]=-1;
}

void add(int u, int v) {
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

void tarjan(int u) {
    low[u]=dfn[u]=++num;
    ins[u]=true;
    s.push(u);
    for(int i=head[u]; i; i=edge[i].next) {
        int v=edge[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u], low[v]);
        }
        else if(ins[v])
            low[u]=min(low[u], dfn[v]);
    }
    if(low[u]==dfn[u]) {
        int v;
        printf("强连通分量：");
        do {
            v=s.top();
            s.pop();
            printf("%d ", v);
            ins[v]=false;
        }while(v!=u);
        printf("\n");
    }
}

int main() {
    
    add(1, 2);
    add(1, 3);
    add(3, 2);
    add(3, 4);
    add(3, 5);
    add(4, 1);
    add(4, 5);
    add(5, 1);
    
    tarjan(1);
    
    return 0;
}

与桥的代码的区别：

桥如果是访问已被访问过的结点，是不用询问该结点是否已入栈了的。

有向图的强连通分量

相关

标签