5.2.8 Tarjan算法

Tarjan算法可用于求解强连通分量以及无向图中的割点和割边（又称桥）

一、连通性概念

那么什么叫强连通分量呢，什么叫割点呢，什么又是割边呢？所以接下来我要从两个方面讲解一下相关的概念

无向图的连通性

无向图中所有能互通（你能到达我，我能到达你）的点组成了一个”连通分量(Connected Component)”。而在一个连通分量中有一些关键的点，如果删掉它们，会把这个连通分量断为两个甚至更多，这种称为 割点(Cut Vertex)。与之类似的，在一个连通分量中如果删除一条边，把这个连通分量分成了两个，这条边成为 割边（Cut Vertex，又称为 桥(bridge)）

而研究割点和割边，我们还能继续拓展出 双连通(Block / 2-Connected Component) 问题，即如何实现一个没有割点和割边的图：

在一个连通图中任选两点，如果他们之间至少存在两条”点不重复”的路径，称为点双连通，一个图中的点双连通极大子图称为 点双连通分量。点双连通分量去掉任意一个点，其他点仍然是连通的，即点双连通分量中没有割点。

类似地，如果任意两点之间至少存在两条”边不重复”的路径，称为 边双连通。边双连通图中，去掉任意一条边，图仍然是连通的，即边双连通图中没有割边。

有向图的连通性

强连通：在有向图G中，如果两个点u和v是互相可达的，则称u和v是强连通的。如果G中任意两点都是互相可达的，称G是强连通图

强连通分量：如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图内部都是强连通的，而且这些子图已经扩展到最大，不能与子图外的任意点强连通，称这样的一个”极大强连通”子图是G的一个强连通分量(Strongly Connected Component，SCC) 有向图中，一些点可以彼此相互到达，这些点就构成一个强连通分量。对于它的处理方式，可以使一个强连通分量缩成一个点，原图就会变成DAG（有向无环图），而因为没有环，所以可以采用拓扑排序。求解强连通分量，掌握Tarjan算法即可。

image-20260522145251641

二、Tarjan算法必备概念

  1. 边分为三种类型：树边、回边、弃边

    树边：没分配过dfn序号

    回边：分配过dfn序号

    弃边：分配过dfn序号，但是还分配过强连通分量

  2. dfn[u]：节点u获得的dfn序号，表示顶点被遍历的顺序

  3. low[u]：u及其子树上的点，最多走一条回边，能到达的树的最上方点，是什么dfn序号。（其实就类似于扎口袋）存储顶点能到达回点的最小时间戳，用于标记强连通关系

  4. belong[u]：节点u分配的强连通分量序号，如果belong[u]为0，表示还没分配

  5. stk[]：栈，用于存储遍历到的节点，遍历到的节点先进栈，一旦该节点分配了强连通分量，就从栈中弹出

还是有点懵是吗，没事，下面让我们代入一个场景

核心设定：时空特工的笔记本

你是一名特工，顺着单行道挨个探索迷宫的据点。每到一个据点，你会在笔记本上记下两组数字：

  1. dfn（到达时间）：你第一次踏入这个据点的绝对时间。
    • 例如：第 1 分钟到了 A，dfn[A]=1；第 2 分钟到了 B，dfn[B]=2。写下后永远不改。
  2. low（能穿越回的最早时间）：这是你的底牌。表示从这个据点继续往下探索，你最多能“抄近道”回到多古老早的时间？
    • 刚到一个据点时，你不知道前路如何，所以先假设只能回到现在，也就是 low = dfn。
  3. 栈 stk（待定区）：所有你走过了、但还没确定到底属于哪个圈的据点，全都在这里排队。

沙盘推演：A -> B -> C -> A（一个完美的闭环）

我们跟着代码走一遍这个最简单的三角圈：

  1. 第一步： 你降落在 A。
    • 时间是 1。A 记录：dfn[A]=1, low[A]=1。
    • A 进入待定区（进栈）。
  2. 第二步： 你从 A 顺着路走到了 B。
    • 时间是 2。B 记录：dfn[B]=2, low[B]=2。
    • B 进入待定区（进栈）。
  3. 第三步： 你从 B 顺着路走到了 C。
    • 时间是 3。C 记录：dfn[C]=3, low[C]=3。
    • C 进入待定区（进栈）。此时栈里是 [A, B, C]。
  4. 第四步（高潮来了）： 站在 C，你发现前方的路指向了 A！
    • 你翻开笔记本，发现 A 已经在待定区（栈）里了，而且 A 的到达时间是 1（dfn[A]=1）。
    • C 狂喜：“我能抄近道回到第 1 分钟！”
    • 于是 C 偷偷篡改了自己的底牌：low[C] = 1。（对应代码：low[x] = min(low[x], dfn[y])）
  5. 第五步（往回汇报）： C 前面没路了，退回到 B。
    • C 对 B 说：“兄弟，我刚探过路了，跟着我走，我们能穿越回第 1 分钟！”
    • B 一听，也赶紧把自己的底牌改了：low[B] = 1。（对应代码：low[x] = min(low[x], low[y])）
  6. 第六步（收网）： B 退回到 A。
    • B 对 A 说：“老大，我能通向第 1 分钟。”
    • A 看了看自己的底牌，本来就是 1，没变：low[A] = 1。
    • 现在 A 发现周围全探索完了，它审视自己：dfn[A] == 1，并且 low[A] == 1。两者相等！（对应代码：if(dfn[x] == low[x])）

这就是 Tarjan 算法最核心的 Aha Moment！

当一个点的 dfn == low 时，意味着什么？ 意味着这个点尽了最大努力，也无法穿越回比它自己更早的时间了。它就是这个圈子里时间最早的人，也就是这个强连通分量的“队长”。

既然队长确认了，队长 A 就大喊一声：“从我之后进入待定区（栈）的所有人，我们组成一个圈，全部出栈！” 于是 C、B、A 依次弹出，他们组成了一个编号为 1 的大圈（SCC）。

为什么一定要判断 instk（是否在栈内）？

想象一下，如果 C 指向的不是 A，而是一个早就被打包成其他圈、已经出栈的据点 Z 呢？

Z 已经是个封闭的历史了，它不属于你当前的探索任务。如果你强行借用 Z 的时间去更新 C 的 low，就会把两个本不相干的单行道强行搅和在一起，导致死循环。

所以代码里有这句： else if(instk[y]) —— 只有当对方还在待定区里（还没被分配到别的圈），我才能借用它的时间。

三、Tarjan算法流程

dfn序号写在左边，low写在右边

一上来，dfn是1，low也是1

image-20260522162212081

然后接着往下走，树边就是两步操作，然后每走过一个点，就入栈

image-20260522162337380

image-20260522162535925

image-20260522162817735

现在看回边的情况，low值从4变成2

image-20260522162923345

image-20260522163302053

回边来到e，g的low值变成5。dfn != low，往上回退

image-20260522163418161

回到f，更改f的low。dfn != low，继续往上回退

image-20260522163540615

回到e点，dfn == low，开始结算

image-20260522163735969

于是记 1：efg

继续操作

image-20260522164120681

image-20260522164232648

h -> g为弃边，无需管

image-20260522164437361

image-20260522164621326

image-20260522164814501

image-20260522165008113

image-20260522165213546

于是记2：hdcba

四、Tarjan算法代码模板

现在，我们进行新一轮的总结：

  1. 全局变量区

    这一块，我们要记录我们的地图、时间戳、手写栈以及最后的收网结果

    1
    2
    3
    4
    vector<int> e[N]; // 地图
    int dfn[N],low[N],idx; // dfn(绝对时间)、low(能回到的最早时间)、idx(全局时钟计数器)
    int stk[N],instk[N],top; //stk(栈)、instk(检查是否入队)、top(队尾指针)
    int scc[N],siz[N],cnt; // scc(每个人属于哪个天团)、siz(该天团的总人数)、cnt(天团总数)

  2. 初入据点

    接下来就是void tarjan(int x)了

    刚到x的时候，赋予绝对时间戳dfn，而同时又暂定最多只能回到当前，所以low也等于它，除此之外，全局时间+1

    而后让x进栈，并更新instk[x] = 1

    1
    2
    dfn[x] = low[x] = ++idx;
    stk[++top] = x,instk[x] = 1;

  3. 探路与抄近道

    这个阶段，x开始遍历所有的子节点y，此时只需要处理两种情况：

    1. 树边（dfn = 0）

      无条件信任下一个子节点，直接派它把y那边全探完：tarjan(y)

      下一个子节点探完回来了，用它打探到的历史底牌更新自我底牌：low[x] = min(low[x],low[y]);

    2. 回边（dfn != 0），当然还要再看这个点在不在栈里

      抄近道，用老熟人y的绝对到达时间更新自我底牌low[x] = min(low[x],dfn[y]);

    1
    2
    3
    4
    5
    6
    7
    8
    for(int y : e[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }else if(instk[y]){
            low[x] = min(low[x],dfn[y]);
        }
    }

  4. 收网

    此时所有需要走的任务都结束了，现在只需要审视自己是不是这个圈子的老大，如果是，就把小弟们全部揪出来

    怎么判断呢？如果我走遍了所有路，发现最多还是回到我自己，那说明我是老大：dfn[x] == low[x]

    先准备小弟变量： int y;

    再申请一个天团编号：++cnt;

    接下来开始收网：

    先从栈顶（最新加进来、最底层的）揪出一个人：y = stk[top--];

    标记他离开栈了：instk[y] = 0;

    给他发队服，表明它是哪个天团的：scc[y] = cnt;

    天团人数+1：++siz[cnt];

    而对于这一层循环，我们的想法是，只要揪出来的这个人不是队长x本人，就说明下面还有人：while(x != y)

    于是有

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if(dfn[x] == low[x]){
        int y; ++cnt;
        do{
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        }while(y != x);
    }

综合代码

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
vector<int> e[N];
int dfn[N],low[N],idx;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;

void tarjan(int x){
    dfn[x] = low[x] = ++idx;
    stk[++top] = x,instk[x] = 1;
    for(int y : e[x]){
        if(!dfn(y)){
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }else if(instk[y]){
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(dfn[x] == low[x]){
        int y; ++cnt;
        do{
            y = stk[top--]; instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        }while(y != x);
    }
}

五、实战

1. P3387 【模板】缩点

门钥匙

Ques

题目描述

给定一个 个点 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 。

第二行 个整数，其中第 个数 表示点 的点权。

第三至 行，每行两个整数 ，表示一条 的有向边。

输出格式

共一行，最大的点权之和。

输入输出样例 #1

输入 #1

1
2
3
4
2 2
1 1
1 2
2 1

输出 #1

1
2

说明/提示

对于 的数据，，，。

Ans

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int N = 1e4+10;
vector<int> e[N];
int dfn[N],low[N],idx;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
vector<int> w(N);

void tarjan(int x){
    dfn[x] = low[x] = ++idx;
    stk[++top] = x,instk[x] = 1;
    for(int y : e[x]){
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }else if(instk[y]){
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(dfn[x] == low[x]){
        int y; ++cnt;
        do{
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            siz[cnt] += w[y];
        }while(y != x);
    }
}

void solve(){
    int n,m; cin >> n >> m;
    
    for(int i = 1;i <= n;++i){
        cin >> w[i];
    }
    for(int i = 1;i <= m;++i){
        int u,v; cin >> u >> v;
        e[u].push_back(v);
    }
    for(int i = 1;i <= n;++i){
        if(!dfn[i]){
            tarjan(i);
        }
    }

    vector<int> dag[N];
    int in_deg[N] = {0};
    int dp[N] = {0};
    for(int u = 1;u <= n;++u){
        for(int v : e[u]){
            if(scc[u] != scc[v]){
                dag[scc[u]].push_back(scc[v]);
                in_deg[scc[v]]++;
            }
        }
    }

    queue<int> q;
    for(int i = 1;i <= cnt;++i){
        dp[i] = siz[i];
        if(in_deg[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : dag[u]){
            dp[v] = max(dp[v],dp[u] + siz[v]);
            in_deg[v]--;
            if(in_deg[v] == 0){
                q.push(v);
            }
        }
    }

    int res = 0;
    for(int i = 1;i <= cnt;++i){
        res = max(res,dp[i]);
    }
    cout << res << '\n';
    return;
}

相关文章

[[5-2-3-Dijkstra]] [[6-6-DSU]]