『并查集』并查集模板

学习并查集前提须知

并查集支持合并与查询，针对于查询某两点是否在同一个树内，或者将两点之间连一条线。

算法内容

竞赛需要用到的点

1、并查集多用于其他算法的过渡使用，不单独考

2、并查集的思路会多次在以后出现，请理解并查集的每一步思路

并查集略讲

并查集是一个很简单的数据结构，其基本思路围绕着一个就是根节点展开，若有两点的根节点相同那么就肯定在一棵树内，所以我们只需要维护一个点的父亲节点就好了，然后每次询问都查找根节点是否相同。

但这是一种最优的情况，若树退化成链的话，很明显，复杂度高了很多，那就和暴力相同，怎样避免这种情况发生呢？我们上面说到，我们只需要判断两点和根节点的关系，那么我们只保留当前点的根节点关系不就好了？的确，这样就能够满足我们的问题了，这样的优化方式我们叫做路径压缩，且这样就出现了图论中的一种特殊图 菊花图，这种图你以后会遇到，多用于卡你的算法，在这里这个不是重点，不再赘述。

那么根据上面的信息我们就可以开始写代码了

部分代码展现

起始化

//#define fre yes

#include <cstdio>

const int N = 1000005;
int par[N], Rank[N]; //Rank表示的是秩优化

void init(int n) {
    for (int i = 0; i <= n; i++) {
        par[i] = i;
        Rank[i] = 1;
    }
}

int main() {
    static int n, m;
    ...
    init(n);
    ...
}

合并操作 + 路径压缩 + 秩优化

int find(int x) {
    if(x == par[x]) return x;
    else return par[x] = find(par[x]);
} //路径压缩（与返回父亲节点）

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return ;
    
    if(Rank[x] <= Rank[y]) par[x] = y;
    else par[y] = x;
    if(Rank[x] == Rank[y]) Rank[x]++;
} //秩优化 与 合并操作

查询操作

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

bool same(int x, int y) {
    return find(x) == find(y);
}

所有代码

//#define fre yes

#include <cstdio>

const int N = 200005;
int par[N], Rank[N];

void init(int n) {
    for (int i = 0; i <= n; i++) {
        par[i] = i;
        Rank[i] = 1;
    }
}

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

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return ;

    if(Rank[x] <= Rank[y]) par[x] = y;
    else par[y] = x;
    if(Rank[x] == Rank[y]) Rank[x]++;
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    static int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    for (int i = 1; i <= m; i++) {
        int k;
        scanf("%d", &k);
        if(k == 1) {
            int x, y;
            scanf("%d %d", &x, &y);
            unite(x, y);
        } else {
            int x, y;
            scanf("%d %d", &x, &y);
            if(same(x, y)) puts("Y");
            else puts("N");
        }
    } return 0;
}