并查集入门——连通分量计数

这道题是为学弟学妹们准备的并查集入门题。希望学弟学妹中能出来一个勤奋努力的高手带社长拿下区域赛金牌！

问题回顾

给定 $m$ 个节点和 $n$ 条无向边，求最少还需添加多少条边才能使整张图连通。

核心思想

一张图如果已经连通，那么任意两点之间都有路径可达。否则，图被分割成若干个连通分量（连通块）。

要把 $k$ 个连通分量连成一整张连通图，至少需要 $k-1$ 条边——就像把 $k$ 个珠子串成一条链，需要 $k-1$ 根线。

答案 = 连通分量数 $\boldsymbol{- 1}$

并查集 (Disjoint Set Union)

并查集是处理连通性问题的利器，支持两个操作：

路径压缩优化

find 时把路径上的节点直接指向根，后续查询接近 $O(1)$：

     1 ← 2 ← 3          find(3) 后 →      1 ← 2
                                              ↖ 3

实现

int parent[MAXN];

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];  // 路径压缩
        x = parent[x];
    }
    return x;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[a] = b;
}

算法流程

1. 初始化：每个节点是自己的代表元素，parent[i] = i
2. 读入每条边，unite(a, b) 合并两个连通分量
3. 遍历所有节点，统计 find(i) == i 的数量（代表元素个数 = 连通分量数 $k$）
4. 输出 $k-1$

复杂度

• 时间：$O(m + n \cdot \alpha(m))$，其中 $\alpha(m)$ 是反阿克曼函数，近似常数
• 空间：$O(m)$

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int parent[MAXN];

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[a] = b;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= m; i++) parent[i] = i;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        unite(a, b);
    }

    int comp = 0;
    for (int i = 1; i <= m; i++) {
        if (find(i) == i) comp++;
    }
    cout << comp - 1 << '\n';
    return 0;
}