C++ 算法技巧 — 连通性 (Connectivity)

章节概述

连通性问题研究图中顶点之间是否连通，是图论最基础也最重要的问题之一。
核心工具包括并查集（静态连通性）、Tarjan（SCC缩点）、SPFA（负环检测）。

核心原理

1. 并查集 — 近乎 O(1) 的连通性查询

两个核心操作 + 两种优化:

find(x): 查找元素所属集合（路径压缩）
merge(x, y): 合并两个集合（按秩合并）

优化后操作复杂度: O(α(n)) ≈ O(1)

2. Tarjan 算法 — 强连通分量 (SCC)

在一次 DFS 中通过维护 dfn 和 low 数组找出所有 SCC:

dfn[u] == low[u] 时，u 是 SCC 的根
栈中 u 以上的节点构成一个 SCC
缩点后得到 DAG

3. 差分约束系统

不等式 $x_{a} - x_{b} \leq c$ 等价于从 b 到 a 权为 c 的边:
$x_{a} \leq x_{b} + c$

用 SPFA 求最短路（无负环则有解）。

关键数据结构

K_并查集_UnionFind — 路径压缩 + 按秩合并
H_图_Graph — 邻接表建图
B_栈_Stack — Tarjan 使用栈保存 SCC

P3367 [模板] 并查集

#include <iostream>
using namespace std;
int fa[10005], rk[10005];
 
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
 
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x, y);
    fa[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
}
 
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) merge(x, y);
        else cout << (find(x) == find(y) ? "Y" : "N") << endl;
    }
    return 0;
}

P5960 [模板] 差分约束算法

题目: 给出 m 个不等式 x_a - x_b ≤ c，求一组合法的解。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 1e9;
int n, m, dist[5005], cnt[5005];
bool inq[5005];
vector<pair<int,int>> g[5005];
 
bool spfa() {
    queue<int> q;
    for (int i = 1; i <= n + 1; i++) {
        dist[i] = 0; cnt[i] = 0;
        inq[i] = true;
        q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (auto [v, w] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v); inq[v] = true;
                    if (++cnt[v] > n + 1) return false;
                }
            }
        }
    }
    return true;
}
 
int main() {
    cin >> n >> m;
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        g[v].push_back({u, w});
    }
    if (!spfa()) cout << "NO" << endl;
    else {
        for (int i = 1; i <= n; i++)
            cout << dist[i] << " ";
        cout << endl;
    }
    return 0;
}

RootStack

探索

C++ 算法技巧 — 连通性 (Connectivity)

章节概述

核心原理

关键数据结构

P3367 [模板] 并查集

P5960 [模板] 差分约束算法

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接