并查集（Union-Find Set）是一种数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种主要操作：union（合并两个集合）和find（查找某个元素属于哪个集合）。这种数据结构在解决连通性问题时非常有用，比如网络中的节点连接、图像处理中的区域标记等。

类 US 的定义

查看代码

class US {
    int[] fa;
    US(int n){
        fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }
    // ... 其他方法 ...
}

在并查集中，通常使用一个整数数组 fa（或称为 parent）来表示每个元素的父节点，数组的索引代表元素，值代表其父节点的索引。

初始时，每个元素的父节点是其自身，即 fa[i] = i。

构造函数 US(int n)：初始化并查集，大小为 n，初始化 fa 数组，使每个元素的父节点指向自己。

方法 find(int x)

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

• find 方法用于查找元素 x 所在集合的代表元素（根节点）。
• 如果 x 等于 fa[x]，则 x 是其所在集合的代表元素，直接返回 x。
• 否则，递归地查找 x 的父节点 fa[x] 的代表元素，并将 x 的父节点设置为找到的代表元素。这个过程称为路径压缩，可以优化查找效率。

方法 merge(int x, int y)

void merge(int x, int y){
    fa[find(x)] = find(y);
}

• merge 方法用于合并元素 x 和 y 所在的集合。
• 首先分别找到 x 和 y 的代表元素。
• 然后将 x 的代表元素的父节点设置为 y 的代表元素，从而将两个集合合并。

在 find 方法中，通过递归查找父节点，并将沿途的每个节点的父节点直接指向根节点，从而实现了路径压缩。这样可以显著提高后续操作的效率。

Java代码

查看代码

class US{
    int[] fa;
    US(int n){
        fa = new int[n];
        for (int i = 0; i < n; i++) {
        	fa[i] = i;
    	}
    }
    int find(int x){
        if(x == fa[x])return x;
        fa[x] = find(fa[x]);
        return fa[x];
    }
    void merge(int x, int y){
        fa[find(x)] = find(y);
    }
}