我们可以使用 tarjan 来求取一张有向图中强连通分量的个数，以及每个强连通分量包含的点的编号．

强连通#

在一张有向图中，如果存在由一些点组成的集合，满足这个集合中的点都可以两两连通，那么称这些点和边为原图的强连通子图．

如果对于一个强连通子图 $T$ ，不存在任意一个其他点在加入 $T$ 后，能够仍然保持强连通子图的性质，那么称 $T$ 为原图的强连通分量．通俗来说，强连通分量就是极大的强连通图．

DFS 生成树#

在有向图上，以任意一个节点为根节点进行一次 DFS，我们可以使用DFS 生成树记录其过程．对于一个节点 A，其子节点 B 满足没有在图上出现过、且有一条边从 A 连接到 B．

DFS 生成树可以辅助将图转换为树 + 边．

示例：

对于上面这条边，如果以 A 为根节点建 DFS 生成树，一种是这样的：

在这张图中，有四种边：

树边：原有的，构成生成树的边除此以外，还有三种额外的边（假定这些边是从节点 $u$ 连接到节点 $v$ 的）：
反祖边： $v$ 是 $u$ 的祖先节点．
前向边： $u$ 不是 $v$ 的父节点，但是是 $v$ 的祖先节点．
横叉边：不是树边、反祖边和前向边的边．

不难发现，每一个强连通分量都至少有一条反祖边．

如何在 DFS 的同时判断一条边是什么边？

我们需要定义一些数据：

bool in_stack[i] 表示点 $i$ 是否在当前 DFS 的路径上．
bool vis[i] 表示点 $i$ 是否被访问过．

	`in_stack` 成立	`in_stack` 不成立
`vis[i]` 成立	反祖边	前向边或横叉边
`vis[i]` 不成立	不可能	树边

Tarjan 求强连通分量#

Tarjan 只需要进行一次 DFS 搜索就能办到．

为了解决问题，我们定义了以下数据：

bool in_stack[i] 表示点 $i$ 是否在当前 DFS 的路径上．
stack<int> s 当前强连通分量中的节点编号．
int dfn[i] 第 $i$ 个点先序遍历到达时间．
int low[i] 第 $i$ 个点通过当前子树内返祖边（即不经过其父节点）回到的最小时间．
无需定义 vis[i]，应为 vis[i] 等效于 dfn[i] == 0．

不难发现：

祖先 dfn 一定小于当前 dfn．
如果一个点 $u$ 能够到达一个点 $v$ ，点 u 的 dfn 大于点 v 的 dfn，那么这样的一组构成了一个强连通分量

对于到达一个新的节点 $u$ ，我们会进行以下操作：

初始化操作
- 初始化 dfn[u]
- 初始化 low[u] = dfn[u]
- 将当前节点入栈 s，并且标记 in_stack．
遍历所有起点为 $u$ $u$ ，终点为 $v$ $v$ 的边
- 如果这条边是反祖边，将 low[u] 进行更新．
- 如果这条边是树边，DFS 搜索节点 $v$ ，然后将 low[u] 进行更新．
- 如果这条边是横叉边或前向边，那么说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作．
检查当前节点是不是一个新的强连通分量的根节点（low[u] == dfn[u]）
- 如果是，那么当前 s 中栈首直到节点 $u$ 存储的就是一个强连通分量．弹出 s 中 $u$ 以上的元素和 $u$ ，还原 in_stack 来处理下一个强连通分量．

时间复杂度分析#

初始化操作： $O(n)$
遍历边操作： $O(m)$
检查节点是不是强连通分量的根节点： $O(n)$

综合一下，时间复杂度 $O(m+n)$

标程#

下面这个程序求解了图中的强连通分量数量和每一个强连通分量的组成部分．

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1e4 + 100;
5

6
int m, n, ans;
7
vector<int> e[N];
8

9
// bool in_stack[i]表示点i是否在当前DFS的路径上．
10
// stack<int> s当前强连通分量中的节点编号．
11
// int dfn[i]第i个点先序遍历到达时间．
12
// int low[i]第i个点通过当前子树内返祖边回到的最小时间．
13
int dfn[N], low[N], cnt;
14
bool in_stack[N];
15
stack<int> s;
16

17
void tarjan(int u)
18
{
19
  if (dfn[u] != 0)
20
    return;
21
  // 初始化
22
  dfn[u] = ++cnt;
23
  low[u] = dfn[u];
24
  in_stack[u] = true;
25
  s.push(u);
26
  // 搜索边
27
  for (auto v : e[u])
28
  {
29
    // 如果是返祖边
30
    if (in_stack[v])
31
    {
32
      // 那么刷新low[u]
33
      low[u] = min(low[u], low[v]);
34
    }
35
    // 如果是树边
36
    else if (!dfn[v])
37
    {
38
      // 递归处理
39
      tarjan(v);
40
      low[u] = min(low[u], low[v]);
41
    }
42
    // 如果是横插边或前向边
43
    else
44
    {
45
      // 节点v已经被处理或将被处理
46
      // 什么也不用做
47
    }
48
  }
49
  // 检查现在的节点是不是强连通分量的根节点．
50
  if (low[u] == dfn[u]) // 如果说这个节点最小只能到达自己
51
  {
52
    // 那么这个节点就是强连通分量的根节点．
53
    ans++;
54
    vector<int> v;
55
    while (s.top() != u)
56
    {
57
      v.push_back(s.top());
58
      in_stack[s.top()] = false;
59
      s.pop();
60

61
    }
62
    v.push_back(s.top());
63
    in_stack[s.top()] = false;
64
    s.pop();
65
    cout << v.size() << " ";
66
    for (auto it : v)
67
    {
68
      cout << it << " ";
69
    }
70
    cout << endl;
71
  }
72
}
73

74
signed main()
75
{
76
  cin >> n >> m;
77
  for (int i = 1; i <= m; i++)
78
  {
79
    int u, v;
80
    cin >> u >> v;
81
    e[u].push_back(v);
82
  }
83
  for (int i = 1; i <= n; i++)
84
  {
85
    tarjan(i);
86
  }
87
  cout << ans << endl;
88
  return 0;
89
}

缩点#

在求出强连通分量之后，我们可以将其缩为一个点，这样缩完之后的图就是一个 DAG 了．

具体来说，可以使用一个数组 belong（常缩写为 bel）记录每一个点所属的强连通分量编号，接下来，对于每一条边，检查其两个连接点，若两个连接点属于不同的强连通分量，则在新图中在这两个强连通分量中代表的点之间连一条边．

1
for (int u = 0; u < n; u++) {
2
  for (auto v : e[u]) {
3
    int a = bel[u], b = bel[v.v];
4
    if (a != b) {
5
      g[a].push_back(b);
6
    }
7
  }
8
}

操作完之后，新的图就是一个有向无环图．

缩点图的逆拓扑序性质

不知道你有没有发现，通过这种方式生成的缩点图中的点排列顺序实际上是逆拓扑序，即所有新图之间的边都满足从编号大强连通分量的连向编号小的，这是由 tarjan 的 dfs 特性决定的．

若根据编号从大到小枚举所有的点，则可以保证在枚举一个点时，所有能够到达它的点都已经被枚举完成了．

音乐

音乐

强连通#

DFS 生成树#

Tarjan 求强连通分量#

时间复杂度分析#

标程#

缩点#

文章分享