并查集

用途

管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点对应集合中的元素.其支持两种操作:

• 合并:合并两个元素所属集合
• 查询:查询某个元素所属集合

模板

private static int[] pre;
// 上级数组初始化
public static void init(int n) {
    pre = new int[n];
    for (int i = 0; i < n; i++) {
        pre[i] = i;
    }
}

// 寻找上级,并将上一级修改为最高的一级
public static int findPre(int key) {
    if (pre[key] == key) {
        return key;
    }
    return pre[key] = findPre(pre[key]);
}

// 联合两个节点,使其拥有共同的上级
public static void unite(int x, int y) {
    int rootx = findPre(x);
    int rooty = findPre(y);
    if (rootx != rooty) {
        pre[rootx] = rooty;
    }
}