Home Tarjan 算法
Post
Cancel

Tarjan 算法

Tarjan 算法

Tarjan 算法是用来求割点和桥的.

时间戳: 用来标记图中每个节点在进行 DFS 时的访问顺序, 用 dfn[x] 来表示.

最早访问时间: 就是要找到从当前节点 x 出发 (将 x 作为搜索树的根节点) 能够访问到的所有节点的最小时间戳. 用 low[x] 来表示.

搜索树: 在无向图中, 如果从某一节点 x 出发进行 DFS, 每一个节点只访问一次, 则所有被访问过的节点与边会构成一棵树, 即“无向连通图的搜索树”.

更新 low 的方法是: 假设图 G 是一个连通图, 从节点 0 出发, 遍历了 m 个节点后到达节点 m. 此时发现 m 除了边 e(m-1,m) 之外, 还有一条边 e(m, 2). 但是节点 2 已经在刚才访问过了, 所以边 e(m, 2) 不是搜索树中的边. 此时, 节点 m 可以通过这条非搜索树边更新自己的 low. 因为节点 2 显然比 m 更早访问, 按照我们的假设应该有 dfs[2]=2, dfs[m]=m, 所以 low[m]=min(low[m], dfs[2])=2. 节点 m 更新为 2 之后, 节点 m-1 是不是也应该更新? 同理, 一直要更新到节点 3 为止.

但是到这里还没结束呢. 这个图不止 m+1 个节点, 例如还有 e(m-1, m+1) 这条边存在. 而 e(m-1, m-2) 和 e(m-1, m) 这两条边已经走过了 (注意这是无向图, e(m-1, m-2) 和 e(m-2, m-1) 是同一条边), 也就是说节点 m-2 和 m 已经访问过了, 所以下一步就是走 e(m-1, m+2) 这条边, 去访问节点 m+1. 显然, 节点 m+1 及其之后被访问的节点是不能更新节点 m-1 及其之前被访问的节点的 low 的, 因为它们的 dfn 一定大于等于 m+1. 所以, 在开启了访问节点 m+1 的这条新路后, 就可以不用去管之前访问过的节点了.

在无向图中, 边 e(u, v) 为桥需要满足: dfn[u] < low[v]. 这个其实很直观了, 意思就是说 v 不能通过除了 u 以外的其他节点访问到时间戳更小的节点, 因此 low[v] 无法被更新为小于等于 dfn[u] 的值. 也就是说, 边 e(u, v) 作为桥梁连接着两个连通子图, 但 u 这边的子图与 v 这边的子图再无其他边相连.

在无向图中, 节点 u 为割点需要满足:

  1. now == root && child >= 2
  2. now != root && dfn[now] <= low[next]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Tarjan(int now,int father,int root){
    dfn[now]=low[now]=++cnt;
    int child=0; //以now为根节点的子树个数
    for(int i=0;i<v[now].size();++i){
        int next=v[now][i];
        if(!dfn[next]){ //next没有被访问过
            if(now==root) child++;
            Tarjan(next,now,root); //访问next
            low[now]=min(low[now],low[next]); //在next被访问的过程中,low[next]可能会被更新,因此low[now]也可能得到更新
            if(now==root&&child>=2)
                cut[now]=true;
            else if(now!=root&&low[next]>=dfn[now]) //low[next]>dfn[now]显而易见,而low[next]==dfn[now]的情况是因为,虽然next不能被now更新(因为now是next的父节点),但是可以被一个既与next连接又与now连接的第三者间接更新
                cut[now]=true;
        }else if(next!=father) //now不能被父节点更新,但可以是除了父节点以外的访问过的节点
            low[now]=min(low[now],dfn[next]);
    }
}
void Build(){
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            Tarjan(i,i,i);
}

模板题

Link

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
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt;
int dfn[20010],low[20010];
vector<int>v[20010];
bool cut[20010];
void Tarjan(int now,int father,int root){
    dfn[now]=low[now]=++cnt;
    int child=0;
    for(int i=0;i<v[now].size();++i){
        int next=v[now][i];
        if(!dfn[next]){
            if(now==root) child++;
            Tarjan(next,now,root);
            low[now]=min(low[now],low[next]);
            if(now!=root&&dfn[now]<=low[next]) cut[now]=true;
        }else if(next!=father)
            low[now]=min(low[now],dfn[next]);
    }
    if(now==root&&child>=2) cut[now]=true;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            Tarjan(i,i,i);
    int ans=0;
    for(int i=1;i<=n;++i)
        if(cut[i]) ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;++i)
        if(cut[i]) printf("%d ",i);
    return 0;
}

PS: 在我之前的两个旧博客里翻了一下, 除了 2020 年 6 月写过两篇和 Tarjan 算法有关的博客之外什么都没有, 而且还是大量复制粘贴的… 我以前写的都是些什么垃圾啊… 然而看过我 GitHub 主页的人, 想看就都可以看到… 真是太丢人了… 这篇其实也好不到哪里去, 不过都是我自己的思考了, 而且我还会放一些题目以及自己的题解的… 望读者 (如果有的话) 谅解.

This post is licensed under CC BY 4.0 by the author.