详解Java实现数据结构之并查集

简介

并查集是一种基于树型结构的数据结构，主要用于解决一些不交集问题。它支持两个操作：

• 合并两个元素所在的集合
• 判断两个元素是否在同一个集合中

在并查集中，每个节点都有一个指向其父节点的指针。如果一个节点的指针指向它本身，说明它是一个集合的根节点。

实现

我们用一个int类型的数组parent来表示每个节点的父节点。初始时，所有节点的父节点都是其本身。

private int[] parent;

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

private int find(int x) {
    if (parent[x] == x) {
        return 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) {
        parent[rootX] = rootY;
    }
}

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

在 find 方法中，我们使用了路径压缩优化，将每个节点直接连接到其根节点。这样，在下次查询时，就能达到更快的查询速度。

在 union 方法中，我们将两个节点所在的集合合并。具体来说，我们将其中一个节点的根节点指向另一个节点的根节点，从而将两个集合合并成一个集合。

在 isConnected 方法中，我们判断两个节点是否在同一个集合中。具体来说，我们比较两个节点的根节点是否相同，如果相同则说明这两个节点在同一个集合中。否则，它们在不同的集合中。

示例说明

示例一

假设原本有三个元素：0，1，2，它们分别在三个不同的集合中。

UnionFind uf = new UnionFind(3);
System.out.println(uf.isConnected(0, 1)); // false
System.out.println(uf.isConnected(1, 2)); // false
System.out.println(uf.isConnected(0, 2)); // false

现在，我们将元素0和元素1合并到同一个集合中。

uf.union(0, 1);
System.out.println(uf.isConnected(0, 1)); // true
System.out.println(uf.isConnected(1, 2)); // false
System.out.println(uf.isConnected(0, 2)); // true

现在，元素0和元素1在同一个集合中，元素2在另一个集合中。

示例二

假设原本有五个元素：0，1，2，3，4，它们分别在五个不同的集合中。

UnionFind uf = new UnionFind(5);
System.out.println(uf.isConnected(0, 1)); // false
System.out.println(uf.isConnected(1, 2)); // false
System.out.println(uf.isConnected(0, 2)); // false
System.out.println(uf.isConnected(3, 4)); // false

现在，我们将元素0和元素1合并到同一个集合中，将元素3和元素4合并到同一个集合中。

uf.union(0, 1);
uf.union(3, 4);
System.out.println(uf.isConnected(0, 1)); // true
System.out.println(uf.isConnected(1, 2)); // false
System.out.println(uf.isConnected(0, 2)); // true
System.out.println(uf.isConnected(3, 4)); // true

现在，元素0和元素1在同一个集合中，元素2在另一个集合中，元素3和元素4在同一个集合中。