Tarjan算法学习总结

发表于

一些概念：

  1. 强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。
  2. 强连通分量(strongly connected components)：在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做强连通分量。
  3. 割点：一个结点称为割点（或者割顶）当且仅当去掉该节点极其相关的边之后的子图不连通。
  4. 桥：一条边称为桥（或者割边）当且仅当去掉该边之后的子图不连通。
  5. dfn[]：保存这个点被第几次搜到。
  6. low[]：保存这个点在或其子树能够追溯到的最早的栈中节点的次序号。

强连通分量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    vis[u]=1;
    sta[++top]=u;//入栈 
    for(int i=0;i<(int)path[u].size();i++){
        int v=path[u][i];
        if(!dfn[v]){//如果没走过 
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]){//如果在栈中 
        	low[u]=min(dfn[v],low[u]);
		}
    }
    if(low[u]==dfn[u]){//回溯到根节点了 
        tot++;
        while(u!=sta[top+1]){//出栈 
            int t=sta[top--];
            vis[t]=0;
            col[t]=tot;//染色 
        }
    }
}

割点：

用cut[]记录这个点是否为割点。

对于根节点，计算其子树数量，如果有2棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。

对于非根节点，如果low[v]>=dfn[u]，此时u就是割点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void tarjan(int u,int fa) {
    int rc=0;//记录根节点的子节点个数 
    dfn[u]=low[u]=++idx;
    for(int i=0; i<(int)path[u].size(); i++) {
        int v=path[u][i];
        if(!dfn[v]) {
            tarjan(v,fa);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=fa) cut[u]=1;
            if(u==fa)rc++;
        }
        low[u]=min(low[u],dfn[v]);
    }
    if(u==fa&&rc>=2)cut[u]=1;
}

桥：

与割点相似，把low[v]>=dfn[u]换成low[v]>dfn[u]（因为不能包括自己）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void tarjan(int u,int fa) {
    int rc=0;//记录根节点的子节点个数 
    dfn[u]=low[u]=++idx;
    for(int i=0; i<(int)path[u].size(); i++) {
        int v=path[u][i];
        if(!dfn[v]) {
            tarjan(v,fa);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])addpath(u,v);
        }
        else if(low[v]<dfn[u]&&u!=fa) {
        	low[u]=min(low[u],dfn[v]);
		}
    }
}

缩点

缩点就是把一个强连通分量看做一个点。

我们用染色来区分每个点属于哪个强连通分量。

对于缩点后的边有两种处理方式：

  • 缩点后枚举每条边，两端点是否属于同一强连通分量，若不属于则建边。
  • 在缩点时每个点出栈时把这个点的边传给它的强连通分量，使其强连通分量指向某个点（注意是缩点前的点）到后面遍历整张图时判断它所指向的点的颜色是否与自己相同。注意此时可能有不止一条边在两个强连通分量之间，所以要标记判断。

鉴于第一种实现方法太简单，这里给出第二种的实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    vis[u]=1;
    sta[++top]=u;
    for(int i=0;i<(int)path[u].size();i++){
        int v=path[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(dfn[v],low[u]);
    }
    if(low[u]==dfn[u]){
        tot++;//tot为这个强连通分量的颜色 
        while(u!=sta[top+1]){
            int t=sta[top--];
            vis[t]=0;
            col[t]=tot;
            for(int i=0;i<(int)path[t].size();i++){
                ve[tot].push_back(path[t][i]);//建立新边 
            }
        }
    }
}
void dfs(int x){//遍历 
    memset(vis,0,sizeof(vis));
    for(int i=0;i<(int)ve[x].size();i++){
        int to=col[ve[x][i]];//to为x指向点的颜色 
        if(vis[to]||to==x)continue;//如果走过或者指向自己 
        vis[to]=1;
        dfs(to);
    }
}