有向图的强连通分量(SCC)

强连通分量 : SCC, 有向无环图 : DAG

介绍：

  • 默认前提为有向图。
  • 连通分量：对于分量中的任意两点 u, v, 必然存在可以从 u 走到 v, 且从 v 走到 u 。
  • 强连通分量 (SCC)：极大连通分量，(无法加入任何点的连通分量)

作用：

  • 将任意一个有向图，通过 缩点 ，转化为有向无环图(拓扑图，DAG)
  • 缩点：将所有连通分量缩成一个点
  • 好处是求最短路或最长路时，可以递推来做，时间复杂度为 线性: O(n + m)

Tarjan算法理论基础：

  • 按照 DFS 的顺序来求
  • 把边分为四类
    • 树枝边 (x, y)：x 是 y 的父节点
    • 前向边 (x, y)：x 是 y 的祖先节点 (x -> y)
    • 后向边 (x, y): 指向祖先节点的边 (y -> x)
    • 横叉边 (x, y): 指向之前搜过的边
  • 如何判断一个点是否在强连通分量中？
    • 情况1：存在后向边直接指向祖先节点
    • 情况2：通过横叉边的后向边走到祖先节点

Tarjan算法求强连通分量(SCC)：

  • 时间戳(timestamp)：根据深度优先遍历的顺序给每个点编号；
    • 对每个点定义两个遍历到 u 的时间戳，
      • dfn[u]: 遍历到 u 的时间
      • low[u]: u 可以遍历到的最小的时间戳
      • 若 u 是其所在强连通分量的最高点，则 dfn[u] == low[u]，可知，u 的强连通分量中不可以加入任何点了，如此就找到了 u 所在的强连通分量。
    • 各种边的性质如下：
      • 树枝边: dfn[y] > dfn[x];
      • 前向边: dfn[y] > dfn[x];
      • 后向边: dfn[y] < dfn[x];
      • 横向边: dfn[y] < dfn[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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    int n, m;
    int h[N], e[M], w[M], ne[M], idx;
    int dfn[N], low[N], timestamp;
    int stk[N], top;
    bool in_stk[N];
    int id[N], scc_cnt, scc_size[N];
    int din[N], dout[N];

    void tarjan(int u)
    {
        dfn[u] = low[u] = ++ timestamp;
        stk[ ++ top] = u, in_stk[u] = true; 
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(!dfn[j]) // 没遍历过
            {
                tarjan(j);
                low[u] = min(low[u], low[j]);
            }
            // 遍历过，且没在任何连通分量中
            else if(in_stk[j]) low[u] = min(low[u], dfn[j]); 
        }

        // 栈中当前点之后的点为一个强连通分量
        if(dfn[u] == low[u])
        {
            ++ scc_cnt;
            int y;
            do {
                y = stk[top -- ];  // 取出栈顶
                in_stk[y] = false; // 不在栈中
                scc_id[y] = scc_cnt;   // 标记为第scc_cnt号强连通分量 
                scc_size[scc_cnt] ++;
            } while(y != u);
        }
    }
  • 缩点：
    1
    2
    3
    4
    5
    6
    7
    for (int i = 1; i <= n; i ++ )
      for (int j = h[i]; ~j; j = ne[j])
      {
          int k = e[j];
          int a = scc_id[i], b = scc_id[k];
          if( a != b) dout[a] ++;
      }
  • 连通分量编号递减的顺序一定为拓扑序，(不用多写一步拓扑排序)
    • 证明：类似 tarjan 算法类似如下的 dfs 求 拓扑排序
    • dfs 求拓扑排序，seq[N] 的逆序一定为拓扑排序
      1
      2
      3
      4
      5
      6
      7
      8
      void dfs(int u)
      {
          for u 的所有邻点：
          {

          };
          seq <- u
      }
    • 可证得，对于 seq 中每个点 u 其后继节点在 seq 中的位置一定在 u 的前面

例题：1174. 受欢迎的牛

代码板子如下：

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, scc_size[N];
int dout[N];

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;
    stk[ ++ top] = u, in_stk[u] = true; 
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt] ++;
        } while(y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    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] ++;
        }
        
    int zeros = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if(!dout[i])
        {
            zeros ++;
            sum += scc_size[i];
            if(zeros > 1)
            {
                sum = 0;
                break;
            }
        }
        
    printf("%d\n", sum);
        
    return 0;
}

常用结论及证明：

结论一：设一个图是非强连通分量，且 tarjan 算法得到的入度为0的点，即起点为P个，出度为0的点，即终点为Q个，把该图变为强连通分量(缩点缩成一个点)，最少需要加几条边？

答：最少需要新加 max(P, Q) 条边，特判掉若 P = Q == 1，则一个边都不用加。

结论一证明：

  • 分析可知 P <= Q 的情况 和 P >= Q 的情况类似，所以下面我们只证明 P <= Q 的情况
  • 当 P == 1 时，可知 P 可到达所有点，所以只需令 Q 个终点都与起点 P 连一条边，则所有路径的点都可以到达起点，即、所有点都可以到达所有点。答案为 Q ，满足 max(P, Q);
  • 当 P > 1 时，可知 Q >= P > 1，则前提 1：必然可以找到两个起点 P1, P2 和两个终点 Q1, Q2，使得 P1 -> …… -> Q1, P2 -> …… -> Q2，一定成立。
    • 简单证明前提 1：
    • 反证法：如果找不到这样的两个点，则必然 Pi -> …… -> Q1 (解释，所有点都走向了 Q1 这个终点，但我们的终点不止 1 个，即、Q > 1，则与已知条件矛盾)，所以必然有 一个 Pj -> …… -> Q2。
  • 从 Q1 连一条边向 P2 ，则 P —, Q — ，起点终点同时 -1。归纳为 加一条边 P, Q同时-1，若去掉 P - 1 次，则此时 P == 1，Q == Q - (P - 1)，此时由之前的 P == 1 的证明可知还需要再加 Q 条边，所以新加的边的总和为：P - 1 + Q - (P - 1) 即为 Q，满足 max(P, Q)
  • 两种情况都成立，故结论成立，得证！

例题：1175. 最大半连通子图

思路：缩点后找最长链(tarjan的强连通分量 + 背包问题求方案数)

例题：368. 银河

思路：强连通分量找正环 + 拓扑排序求最长路