并查集与连通性问题

算法数据结构并查集

算法

发布日期: 2024-09-27

作者: 小乐

文章字数: 437

阅读时长: 2 分

阅读次数:

一、并查集概述

1.1 支持操作

Find：查找元素所属集合（根）
Union：合并两个集合

1.2 应用场景

连通分量
最小生成树(Kruskal)
等价关系
离线查询

二、基本实现

2.1 数组版

class UnionFind {
    int[] parent;
    int[] rank;  // 按秩合并
    int count;   // 连通分量数
    
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    // 路径压缩
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩
        }
        return parent[x];
    }
    
    // 按秩合并
    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        count--;
        return true;
    }
    
    boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

三、复杂度分析

3.1 反阿克曼函数

经过路径压缩和按秩合并优化后，单次操作均摊复杂度为 ( O(\alpha(n)) )，其中 ( \alpha ) 是反阿克曼函数，增长极慢（实际中可视为常数）。

四、经典应用

4.1 省份数量

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) uf.union(i, j);
        }
    }
    return uf.count;
}

4.2 冗余连接

public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) return edge;
    }
    return new int[0];
}