边双连通分量 (EBCC) 模板详解

边双连通分量 (EBCC) 模板详解

1. 简介

边双连通分量(Edge Biconnected Component, EBCC)是指图中的一个极大子图，其中任意两点之间至少存在两条边不重复的路径。本模板实现了边双连通分量的计算，同时可以找出图中的割点(Cut Vertex)和桥(Bridge)。

主要特点：

  • 支持无向图的边双连通分量分解
  • 可以识别割点和桥
  • 支持图的压缩
  • 时间复杂度 O(V + E)

2. 实现原理

2.1 基本概念

  1. 边双连通分量：

    • 极大的边双连通子图
    • 子图中任意两点间至少有两条边不重复的路径

  2. 割点与桥：

    • 割点：删除后会增加图的连通分量数的点
    • 桥：删除后会增加图的连通分量数的边

2.2 核心策略

  1. Tarjan算法：

    • 使用 DFS 遍历图
    • 维护时间戳(dfn)和追溯值(low)
    • 通过比较 dfn 和 low 识别割点和桥

  2. 压缩策略：

    • 将每个边双连通分量压缩为一个点
    • 构建压缩后的新图

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
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
struct EBCC {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<int> dfn, low, bel;
    std::vector<int> stk;
    int cur, cnt;
    
    // 构造函数
    EBCC() {}
    EBCC(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);
        adj[v].emplace_back(u);
    }
    
    // DFS过程
    void dfs(int x, int p) {
        dfn[x] = low[x] = cur++;
        stk.emplace_back(x);
        
        int child = 0;
        for (auto y : adj[x]) {
            if (y == p) continue;
            if (dfn[y] == -1) {
                child++;
                E.emplace(x, y);
                dfs(y, x);
                low[x] = std::min(low[x], low[y]);
                // 判断割点
                if (low[y] >= dfn[x] && p != -1) {
                    point.emplace(x);
                }
                // 判断桥
                if (low[y] > dfn[x]) {
                    bridge.emplace(x, y);
                }
            } else if (bel[y] == -1 && dfn[y] < dfn[x]) {
                E.emplace(x, y);
                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++;
        }
        
        // 根节点特判
        if (p == -1 && child >= 2) {
            point.emplace(x);
        }
    }
    
    // 计算边双连通分量
    std::vector<int> work() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(i, -1);
            }
        }
        return bel;
    }
    
    // 图压缩
    struct Graph {
        int n;
        std::vector<std::pair<int, int>> edges;
        std::vector<int> siz;
        std::vector<int> cnte;
    };
    
    Graph compress() {
        Graph g;
        g.n = cnt;
        g.siz.resize(cnt);
        g.cnte.resize(cnt);
        for (int i = 0; i < n; i++) {
            g.siz[bel[i]]++;
            for (auto j : adj[i]) {
                if (bel[i] < bel[j]) {
                    g.edges.emplace_back(bel[i], bel[j]);
                } else if (i < j) {
                    g.cnte[bel[i]]++;
                }
            }
        }
        return g;
    }
};

4. 函数说明

4.1 构造和初始化

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

4.2 核心操作

1
2
3
void addEdge(int u, int v)
std::vector<int> work()
Graph compress()
  • addEdge: 添加无向边
  • work: 计算边双连通分量
  • compress: 压缩图结构

5. 时间复杂度分析

  • 初始化：O(V)

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

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

    • DFS遍历：O(V + E)
    • 压缩图构建：O(V + E)

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

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

6. 应用场景

  1. 网络可靠性分析
  2. 图的连通性研究
  3. 关键边和关键点识别
  4. 图的结构分析
  5. 网络设计优化

7. 使用示例

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

// 添加边
ebcc.addEdge(0, 1);
ebcc.addEdge(1, 2);
ebcc.addEdge(2, 3);
ebcc.addEdge(3, 1);
ebcc.addEdge(3, 4);

// 计算边双连通分量
auto bel = ebcc.work();

// 获取压缩后的图
auto g = ebcc.compress();

// 输出每个点所属的分量
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 算法高效实现了EBCC的计算。通过识别割点和桥，以及图的压缩功能，为图的结构分析提供了强大的工具。