并查集

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 648 字

路径压缩 + 按秩合并，近乎 O(1) 判连通

数据结构
并查集

前置内容

数组遍历

正文

// 并查集：维护集合连通性
// 找根 find + 合并 union
// 路径压缩 + 按秩合并
// 近乎 O(1) 判两点是否同集
#include <cstdio>
int fa[10005], rk[10005];
// 找根：顺链上溯并压缩
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
// 合并：挂到秩更大的根下
void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rk[rx] < rk[ry]) fa[rx] = ry;
    else {
        fa[ry] = rx;
        // 秩相等时抬高 rx
        if (rk[rx] == rk[ry]) rk[rx]++;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    // 初始化：各自为独立集合
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rk[i] = 0;
    }
    printf("%d", find(1) == find(2));
    return 0;
}

并查集

前置内容

正文

CSP-J · 编程模板的其它内容