C语言数据结构之并查集总结

简介

并查集，也称作不相交集合，是一种树型的数据结构。并查集用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

并查集只有两个操作：

• find：确定某个元素属于哪个子集。它可以被用来确定两个元素是否属于同一子集。
• union：将两个子集合并成同一个集合。

基本实现

以快速查找find和按秩合并rank为例：

const int MAXN = 1010;
int f[MAXN], rank[MAXN];

void makeSet(int n) {
    for(int i = 0; i <= n; i++) {
        f[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if(f[x] == x) {
        return x;
    } else {
        return f[x] = find(f[x]);
    }
}

void unionSet(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if(fx == fy) {
        return;
    }
    if(rank[fx] < rank[fy]) {
        f[fx] = fy;
    } else {
        f[fy] = fx;
        if(rank[fx] == rank[fy]) {
            rank[fx]++;
        }
    }
}

应用示例

连通块数量

题目描述：

有一个n个点m条边的无向图，求连通块的数量。

根据题目可以建立一个n个元素的集合，每个元素代表一个点，首先将每个元素与自身合并，然后每遇到一条边，将两个点所在的集合合并，最后求并查集中不同簇的数目即为连通块的数量。

代码示例：

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    makeSet(n);
    while(m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        unionSet(x, y);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(f[i] == i) {
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

判断是否为一棵树

题目描述：

给定一个无向图，判断它是否是一棵树。

根据树的定义，首先它必须是一个连通图，其次没有环，所以我们每遇到一条边，就要判断两个点是否已经在同一集合下，如果是，在操作这条边便产生了环。最后检查连通块数和边数是否符合树的要求即可。

代码示例：

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    makeSet(n);
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if(find(x) != find(y)) {
            unionSet(x, y);
        } else {
            cnt++;
        }
    }
    if(cnt == 0 && n - 1 == m) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}