路人乙の小窝

我若安好，万事大吉

0%

Tarjan算法

发表于 分类于

前言

我在去年十月份的博客写过这样一句话：

之前遇到好多题题解有拓扑排序+一堆其他图论算法，包括求强连通分量、缩点等，并不像我最近刷的模板题那么简单。所以我打算下一步去复习Tarjin算法，以防真遇到题发现自己只会一半（笑）。

于是我来复习了）

Tarjan算法用途

  1. 求无向图割点、割边
  2. 求有向图强连通分量、缩点得到DAG
  3. 以后遇到再写

预备知识

  1. dfs搜索树：根据dfs的性质，在无向连通图或有向图的强连通分量中应该会不重不漏的访问所有节点，根据搜索的顺序可以得到一颗生成树，记这颗树为dfs搜索树
  2. dfs时间戳：在dfs的过程中根据访问的顺序为每个结点分配一个时间戳，记作dfn，显然每个结点的dfn是不一样的
  3. 树边：在dfs搜索树的n个结点只由n-1条边连接，这n-1条边均为树边
  4. 非树边：在原图中存在，但是在dfs搜索树中不存在的边
  5. 返祖边：根据dfs的性质，每一条非树边连接的两个边一定有子孙关系，记这两个结点为u、v，且在dfs搜素树中深度较大的点为v，那么LCA(u, v) = u 一定成立，定义以每个结点为端点，连接这个端点与其祖先的边为返祖边。

一点点备注

  1. 根据存边的方式、dfs的方式等的变化，同一个图可能得到不同的dfs搜索树
  2. 为什么LCA(u, v) = u一定成立？若u与v由一条非树边e连接，若v不为u的祖先，u总可以通过dfs向下访问到v，此时e为树边，与假设相反

LOW数组

考虑这样一个问题：如何求出一个无向联通图中所有的割点？

  1. 我们将图退化为树，树中每一个度不小于2的结点都是割点
  2. 在dfs搜索树中考虑：对于非根的结点u，如果其每一棵子树都存在结点v，使得结点v存在返祖边(v,f(u))，那么u一定不为割点（其中f(u)为u的祖先结点且f(u)不为u）
  3. 反之，如果对于结点u，如果u存在子树，其中任意结点v都补存在返祖边(v,f(u))，那么u为割点

那问题可以转化为判断结点u子树中是否有返祖边连接到u的祖先。

记low[u]为u可回溯到的dfn最小的结点，以下为求low[u]的步骤：

  1. 访问所有与u相连的结点v（原图中）
  2. 如果v已经被访问过（dfn不为0），令low[u] = min(low[u], dfn[v])
  3. 否则，对v递归执行算法，令low[u] = min(low[u], low[v])
  4. 重复1-3

Tarjan求割点

传送门

在介绍low数组时，为了突出重点，我们没有考虑根节点。实际上，由于root不存在祖先节点f(root)，我们只需要考虑root的子树数量。如果子树数量>=2，root也为割点。

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
#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 7;
const int M = 1e5 + 7;

vector<int> G[N];
vector<int> cuts;
int dfn[N], low[N], dn = 0;
int child = 0, root = 1;
void tarjan(int u) {
	dfn[u] = low[u] = ++dn;
    bool iscut = false;
    for(int v : G[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
			if(u == root) child++;
            else if(low[v] >= dfn[u]) iscut = true;
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if(iscut) cuts.push_back(u);
}

int n, m;
int main() {
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; ++i) {
		cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for(int i = 1; i <= n; ++i) {
        if(!dfn[i]) {
            root = i;
            child = 0;
            tarjan(root);
            if(child >= 2) cuts.push_back(root);
        }
    }

    sort(cuts.begin(), cuts.end());
    cout << cuts.size() << endl;
    for(int i : cuts) cout << i << " ";
}

Tarjan求有向图强连通分量

传送门

我们以如下方式计算有向图的low数组：

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

我们用一个栈来保存结点，在对每个点执行tarjan时将其入栈，在tarjan执行完成后判断dfn[x] == low[x]，如果为真，则x是一个强连通分量的起点，否则不是。强连通分量中的结点为栈中从栈顶到x所有的结点。

为什么？

先证必要性：

首先对于结点u，low[u]一定是不大于dfn[u]的。

记结点u所在的强连通分量为SCC，如果low[u] < dfn[u]，那么说明存在结点w为u的祖先节点在SCC中，所以从栈顶到u的元素不为完整的强连通分量。

再证充分性：

假设对于满足low[u] == dfn[u]的u，从栈顶到u中存在元素v不属于SCC：

  1. low[v] == dfn[v]，这说明v是另一个强连通分量的起点，应该会在tarjan(v)过后出栈，这与假设不符
  2. low[v] < dfn[v]
    1. low[v] < dfn[u]: 此时low[u]应该被更新为更小的low[v]，与假设不符
    2. low[v] >= dfn[u]: 此时v属于SCC，与假设不符

综上，算法的正确性得到证明。

洛谷这道题需要在求出SCC后注意输出顺序

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 7;
int n, m;
vector<int> G[N];
int fa[N];
vector<int> ans[N];
int low[N], dfn[N], dn = 0, cnt = 0;
stack<int> s;
bool instk[N];
void tarjan(int x) {
    low[x] = dfn[x] = ++dn;
    instk[x] = true;
    s.push(x);
    for(int y : G[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]) {
        cnt++;
        int y;
        do {
            y = s.top();    s.pop();
            instk[y] = false;
            ans[x].push_back(y);  
            fa[y] = x;
        } while(y != x);
    }
}

int main() {
    cin >> n >> m;
    set<pair<int, int>> st;
    for(int u, v, i = 1; i <= m; ++i) {
        cin >> u >> v;
        if(u != v && st.find({u, v}) == st.end()) {
            st.insert({u, v});
            G[u].push_back(v);
        }
    }

    for(int i = 1; i <= n; ++i) {
        if(dfn[i] == 0) {
            tarjan(i);
        } 
    }

    cout << cnt << endl;
    set<int> st2;
    for(int i = 1; i <= n; ++i) {
        if(!st2.count(fa[i])) {
            sort(ans[fa[i]].begin(), ans[fa[i]].end());
            for(int j = 0; j < ans[fa[i]].size(); ++j) {
                cout << ans[fa[i]][j] << " \n"[j == ans[fa[i]].size() - 1];
            }
            st2.insert(fa[i]);
        }
    }

    return 0;
}

缩点

缩点的步骤和强连通分量差不多，本质是求出强连通分量，取一点为代表，建出新的图。得到新的图为DAG，可以结合toposort进行一些操作

传送门

这道题是很经典的缩点+拓扑排序，码量有100行，但是思维难度其实不大。做出这题应该也算我学有所成了。

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
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 1;
int n, m;
vector<int> G[N], DAG[N];
int val[N];
int fa[N], in[N];
int dp[N];

int low[N], dfn[N], dn = 0;
stack<int> s;
bool instk[N];
void tarjan(int x) {
    low[x] = dfn[x] = ++dn;
    instk[x] = true;
    s.push(x);
    for(int y : G[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;
        do {
            y = s.top();    s.pop();
            instk[y] = false;   
            fa[y] = x;
            val[x] += val[y];
        } while(y != x);
        val[x] >>= 1;
        in[x] = 0;
    }
}

vector<int> L;
void toposort() {
    queue<int> q;  
    for(int i = 1; i <= n; ++i) {
        if(fa[i] == i && in[i] == 0) q.push(i); 
    }

    while(!q.empty()) {
        int u = q.front();    q.pop();
        L.push_back(u);
        for(int v : DAG[u]) {
            if(--in[v] == 0) q.push(v);
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> val[i];
    for(int u, v, i = 1; i <= m; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
    }

    for(int i = 1; i <= n; ++i) {
        if(dfn[i] == 0) {
            tarjan(i);
        } 
    }

    set<pair<int, int>> st;
    for(int i = 1; i <= n; ++i) {
        for(int j : G[i]) {
            if(fa[i] == fa[j] || st.count({fa[i], fa[j]})) continue;
            DAG[fa[i]].push_back(fa[j]);
            st.insert({fa[i], fa[j]});
            in[fa[j]]++;
        }
    }

    toposort();

    int ans = -1;
    for(int i : L) {
        if(dp[i] == 0) dp[i] = val[i];
        for(int j : DAG[i]) {
            dp[j] = max(dp[j], dp[i] + val[j]);
        }
        ans = max(dp[i], ans);
    }

    cout << ans << endl;
}

后记

昨天下午做一些树上问题时想到了这个困扰了我很久的tarjan算法。初三寒假的时候我在SDOI冬令营第一次接触tarjan算法，说实话课上一点也没有理解，当时晚上在机房熬到很久才照着一本通缩点写了60分（tarjan部分应该是对的，当时不会toposort和树形dp），但是还是对这个算法有着很多疑惑，没有彻底理解。

现在数学水平和思维水平比当时都有所提高了，花了半天的功夫把洛谷上三道模板题啃了下来，并写了这篇题解，送给五年前的自己。

我很可爱，请给我钱qwq