强连通分量 (SCC) 模板详解

强连通分量 (SCC) 模板详解

1. 简介

强连通分量(Strongly Connected Component, SCC)是有向图中的一个极大子图，其中任意两点之间都存在相互可达的路径。本模板使用 Tarjan 算法实现了强连通分量的计算。

主要特点：

  • 支持有向图的强连通分量分解
  • 基于 Tarjan 算法实现
  • 时间复杂度 O(V + E)
  • 可用于缩点构建DAG

2. 实现原理

2.1 基本概念

  1. 强连通分量：

    • 有向图中的极大强连通子图
    • 子图中任意两点互相可达

  2. Tarjan算法：

    • 基于DFS的单次遍历算法
    • 使用时间戳和追溯值识别强连通分量

2.2 核心策略

  1. DFS遍历：

    • 维护时间戳(dfn)记录访问顺序
    • 维护追溯值(low)记录可追溯的最早时间戳

  2. 栈维护：

    • 使用栈记录访问路径
    • 当dfn[x] = low[x]时找到一个强连通分量

3. 模板代码

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
struct SCC {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<int> stk;
    std::vector<int> dfn, low, bel;
    int cur, cnt;
    
    // 构造函数
    SCC() {}
    SCC(int n) {
        init(n);
    }
    
    // 初始化
    void init(int n) {
        this->n = n;
        adj.assign(n, {});
        dfn.assign(n, -1);
        low.resize(n);
        bel.assign(n, -1);
        stk.clear();
        cur = cnt = 0;
    }
    
    // 添加有向边
    void addEdge(int u, int v) {
        adj[u].emplace_back(v);
    }
    
    // DFS过程
    void dfs(int x) {
        dfn[x] = low[x] = cur++;
        stk.emplace_back(x);
        
        for (auto y : adj[x]) {
            if (dfn[y] == -1) {
                dfs(y);
                low[x] = std::min(low[x], low[y]);
            } else if (bel[y] == -1) {
                low[x] = std::min(low[x], dfn[y]);
            }
        }
        
        // 找到强连通分量
        if (dfn[x] == low[x]) {
            int y;
            do {
                y = stk.back();
                bel[y] = cnt;
                stk.pop_back();
            } while (y != x);
            cnt++;
        }
    }
    
    // 计算强连通分量
    std::vector<int> work() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(i);
            }
        }
        return bel;
    }
};

4. 函数说明

4.1 构造和初始化

1
2
3
SCC()
SCC(int n)
void init(int n)
  • 支持默认构造和指定大小构造
  • 初始化所有必要的数组和变量

4.2 核心操作

1
2
void addEdge(int u, int v)
std::vector<int> work()
  • addEdge: 添加有向边
  • work: 计算强连通分量并返回每个点所属的分量编号

5. 时间复杂度分析

  • 初始化：O(V)

    • 数组分配：O(V)
    • 变量初始化：O(1)

  • 核心操作：O(V + E)

    • DFS遍历：O(V + E)
    • 栈操作：O(V)

  • 空间复杂度：O(V + E)

    • 邻接表：O(E)
    • 辅助数组：O(V)

6. 应用场景

  1. 有向图的环检测
  2. 2-SAT问题求解
  3. 游戏关卡依赖分析
  4. 社交网络社群发现
  5. 编译依赖分析

7. 使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 创建并初始化SCC
int n = 5;  // 节点数
SCC scc(n);

// 添加有向边
scc.addEdge(0, 1);
scc.addEdge(1, 2);
scc.addEdge(2, 0);
scc.addEdge(2, 3);
scc.addEdge(3, 4);

// 计算强连通分量
auto bel = scc.work();

// 输出每个点所属的分量
for (int i = 0; i < n; i++) {
    std::cout << "Node " << i << " belongs to component " << bel[i] << "\n";
}

8. 注意事项

  1. 输入必须是有向图
  2. 节点编号从0开始
  3. 强连通分量编号不保证按拓扑序
  4. 多个连通分量的情况会自动处理

9. 总结

强连通分量是有向图分析中的重要工具，本模板通过 Tarjan 算法高效实现了SCC的计算。它可以用于解决各种图论问题，特别是在需要处理有向图的环结构时非常有用。