并查集专题

1.并查集模板

并查集是一种树型数据结构(多叉树)，可以高效地实现查找和合并功能，常用于求连通问题

1.每个数据可以看作一个节点

2.每一组数据都是一颗树

3.一个组中的数据对应的树和另外一个组中数据对应的树之间没有任何关系

4.初始化的时候把索引当作每个组的标识符

并查集主要有三个功能：

1.寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个

2.将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上

3.判断两个节点是否在同一个集合，函数：same(int u, int v)，就是判断两个节点是不是同一个根节点

int n = 1005; // 节点数量3 到 1000
int[] father = new int[n]; // father[i]为节点i的父亲

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

// 并查集寻根
int find(int u) {
    // return u == father[u] ? u : father[u] = find(father[u]);
    if(father[u]!=u) father[u]=find(father[u]); // 递归返回的同时压缩路径
    return father[u];
}

// 将v->u 这条边加入并查集(合并:其中u为根节点)
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    father[v] = u;
}

// 判断 u 和 v 是否位于同一个连通域(同根)
boolean same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

注意： 每个连通域根节点都是独一无二的，因此可以通过某个节点寻根+HashMap统计出每个连通域的节点数量以及连通域个数等，而不用多一个字段值sum，代码如下：

// 根据图的信息构建连接
for (int[] e : edges) {
    join(e[0], e[1]);
}
// 由于每个连通块的根都是唯一的,因此我们可以利用此来统计连通块内的元素个数
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
    int root = find(i); // 该连通域对应的根节点
    map.put(root, map.getOrDefault(root, 0) + 1);
}

map.size()就是连通域数量；map.get(find(x))就是节点x所在连通域节点数量