并查集数据结构详解与实战应用 | 极客日志

Javajava算法

并查集数据结构详解与实战应用

并查集用于管理不相交集合，核心支持查找与合并操作。通过路径压缩和按秩合并优化，时间复杂度接近常数。本文详解其原理、实现细节及在图连通性、社交网络等场景的应用，结合 LeetCode 实例演示动态连通性问题的解法。

安卓系统发布于 2026/3/24更新于 2026/5/23 浏览

并查集数据结构详解与实战应用

一、认识并查集

1. 定义

并查集（Disjoint Set Union, DSU）是一种用于管理不相交集合的数据结构。它主要用于处理需要动态维护集合合并和查询的问题。核心功能高效支持两个基本操作：

Find（查找）：确定某个元素属于哪一个集合。
Union（合并）：将两个元素所在的集合合并为一个集合。

2. 基本概念

2.1 集合表示

并查集通常通过一个数组（parent 数组）来表示每个元素的父节点，形成森林结构。每个集合用一棵树表示，根节点即为该集合的代表元素。

例如，5 个元素（0~4）初始时各自独立：

0 1 2 3 4

对应的 parent 数组为 [0, 1, 2, 3, 4]，每个元素的父节点指向自己。

2.2 合并操作

合并两个集合时，将一个集合的根节点指向另一个集合的根节点。例如合并元素 1 和 0：

0 1 2 3 4
 \ /
  1

此时 parent 数组变为 [1, 1, 2, 3, 4]，根节点为 1。

2.3 查询操作

查询元素所属集合即找到其所在树的根节点。例如 find(0) 会沿父节点向上直到根。

3. 核心实现与优化

3.1 初始化

初始化时，每个元素的父节点指向自己，秩（rank）设为 0。

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
}

3.2 查找与路径压缩

查找根节点时，使用路径压缩技术可将查找路径上的所有节点直接指向根，减少后续查找深度。

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

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX] += 1;
        }
    }
}

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public static void main(String[] args) {
        int n = 10;
        UnionFind uf = new UnionFind(n);
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(6, 7);
        
        System.out.println("Is 1 and 5 connected? " + uf.isConnected(1, 5)); // true
        System.out.println("Is 1 and 3 connected? " + uf.isConnected(1, 3)); // false
    }
}

private int N;
public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int swimInWater(int[][] grid) {
    this.N = grid.length;
    int len = N * N;
    int[] index = new int[len];
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            index[grid[i][j]] = getIndex(i, j);
        }
    }

    UnionFind uf = new UnionFind(len);
    
    for (int i = 0; i < len; i++) {
        int x = index[i] / N;
        int y = index[i] % N;
        
        for (int[] d : DIRECTIONS) {
            int newX = x + d[0];
            int newY = y + d[1];
            if (inArea(newX, newY) && grid[newX][newY] <= i) {
                uf.union(index[i], getIndex(newX, newY));
            }
        }
        
        if (uf.isConnected(0, len - 1)) {
            return i;
        }
    }
    return -1;
}

private int getIndex(int x, int y) {
    return x * N + y;
}

private boolean inArea(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

class UnionFind {
    private int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) parent[rootP] = rootQ;
    }
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

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

class UnionFind {
    int[] root;
    int[] rank;
    int count;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (x == root[x]) return x;
        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}