【图论】图文详解Tarjan算法有向图缩点

一、前言

在处理有向图的题目中，我们往往会遇到一个知识点 ---- 强连通分量。简单来说，在有向图中，可能存在一部分的点，在这一部分的点中，任意两个点都可以通过有限的步数彼此到达，这些点可能由一个环或者几个环构成。而在有向图中，每一个强连通分量中的点在某些情况下可以看作一个点，因此我们可以把整个图重新转化为一个有向无环图来解决某些问题。

二、前置知识点

• 链式前向星建图
• 强连通分量概念
• 有向图的DFS遍历序

三、算法流程介绍

1.有向图建图

在这张图中，点集 [2 , 3 , 4 , 6]是一个强连通分量，我们希望把这张图变成这样

2.设置变量

而在dfs遍历之前，我们需要了解几个数组变量的含义
dfn[i]:代表编号为 i 的点的DFS序序号
low[i]:代表编号为 i 的点所在的强连通分量中所有点中的最小dfn值
timestamp:时间戳
id[i]:缩点之后重新给点编号
sz[i]:每个强连通分量的点的数量
stk:栈，代表所有已经遍历到的但是还没有遍历完所有的边的节点
in_stk[i]:标记这个点是否在栈中

3.DFS遍历

1) 进入一个没有遍历过的点，更新dfn[u] = low[u] = ++timestamp

2) 遍历所有的边 u—>j 如果发现j点还没有被遍历过，dfs(j),之后更新low[u] = min(low[j] , low[u])

3) 如果发现j点已经在栈中，更新low[u] = min(low[u] , dfn[j])

对于边 4 —> 3

对于边 4 —> 2

4) 当一个点u遍历完了所有的边后，检查dfn[u]是不是等于于low[u]，如果是，则不停的弹出栈顶元素直到栈顶元素是自己，这个操作中所有弹出的点都和节点u同属于一个强连通分量，可以缩为一个点，分配一个id编号。

dfs遍历完点5，4，6，3，7后：

dfs(2)遍历完后：

dfs(1)遍历完后：

最后缩完点后的图为：

简化后：

5 小性质
当缩点缩完后我们发现，4，3，2，1就是缩点后的图的拓扑排序

四、代码解释

void tarjan(int u)
{
  dfn[u] = low[u] = ++timestamp;         //用时间戳给dfn与low赋值
  stk[++tt] = u, in_stk[u] = true;       //把点u放进栈中
  for (int i = h[u]; ~i; i = ne[i])      //链式前向星遍历
  {
    int j = e[i];
    if (!dfn[j])      //如果还没被遍历过
    {
      tarjan(j);                         //递归tarjan
      low[u] = min(low[u], low[j]);      //赋值low
    }
    else if (in_stk[j])      //如果在栈中就更新以下low
    {
      low[u] = min(low[u], dfn[j]);
    }
  }
  if (dfn[u] == low[u])      //如果遍历完所有点后dfn[u]仍然等于low[u]
  {
    ++scc_cnt;      //强连通分量编号
    int v;
    do      //把栈中的点加入强连通分量
    {
      v = stk[tt--];
      in_stk[v] = false;
      id[v] = scc_cnt;
      sz[scc_cnt]++;
    } while (v != u);
  }
}
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

完整缩点代码：

//#pragma GCC optimize(2)
#include 
#define endl '\n'
#define el endl
#define pb push_back
#define int long long
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define with << ' ' <<
#define print(x) cout << (x) << endl
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define f(i, l, r) for (int i = (l); i <= (r); i++)
#define ff(i, l, r) for (int i = (l); i >= (r); i--)
#define pr(x, n) f(_, 1, n) cout << (x[_]) << " \n"[_ == n];
#define ck(x) cerr << #x << "=" << x << '\n';
using namespace std;
typedef pair PII;
const int N = 1e6 + 7, mod = 1e9 + 7;

int n, m;
int h[N], e[N], ne[N], idx;
int dfn[N], low[N], timestamp;
int stk[N], tt;
bool in_stk[N];
int id[N], sz[N], scc_cnt;      //查找新点id，id中点的数量，新点总数
int din[N], dout[N];

void init()
{
  memset(h, -1, sizeof h);
  for (int i = 0; i <= n * 10; i++)
  {
    in_stk[i] = false;
    dfn[i] = low[i] = stk[i] = id[i] = sz[i] = din[i] = dout[i] = 0;
    idx = timestamp = tt = scc_cnt = 0;
  }
}

void add(int a, int b)
{
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u)
{
  dfn[u] = low[u] = ++timestamp;         //用时间戳给dfn与low赋值
  stk[++tt] = u, in_stk[u] = true;       //把点u放进栈中
  for (int i = h[u]; ~i; i = ne[i])      //链式前向星遍历
  {
    int j = e[i];
    if (!dfn[j])      //如果还没被遍历过
    {
      tarjan(j);                         //递归tarjan
      low[u] = min(low[u], low[j]);      //赋值low
    }
    else if (in_stk[j])      //如果在栈中就更新以下low
    {
      low[u] = min(low[u], dfn[j]);
    }
  }
  if (dfn[u] == low[u])      //如果遍历完所有点后dfn[u]仍然等于low[u]
  {
    ++scc_cnt;      //强连通分量编号
    int v;
    do      //把栈中的点加入强连通分量
    {
      v = stk[tt--];
      in_stk[v] = false;
      id[v] = scc_cnt;
      sz[scc_cnt]++;
    } while (v != u);
  }
}

void solve()
{
  cin >> n >> m;
  init();
  for (int i = 1; i <= m; i++)
  {
    int x, y;
    cin >> x >> y;
    add(x, y);
  }
  for (int i = 1; i <= n; i++)
  {
    if (!dfn[i])
      tarjan(i);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = h[i]; ~j; j = ne[j])
    {
      int k = e[j];
      int a = id[i], b = id[k];
      if (a != b)
        dout[a]++, din[b]++;
    }
  }
}

signed main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  // clock_t start_time = clock();
  int __ = 1;
  //    cin>>__;
  //    init();
  while (__--)
    solve();
  // clock_t end_time = clock();
  // cerr << "Running time is: " << ( double )(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
  return 0;
}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

作者：Avalon·Demerzel
喜欢的话就请点个赞吧，更多内容详见专栏《图论与数据结构》