并查集【模板】

思路
并查集：树形数据结构
find函数(查找所有结点的根结点)：

int find(int x){
    if(f[x]==x) return x;//如果结点本身就是根结点，直接返回自己
    else return f[x]=find(f[x]);//否则通过路径压缩递归返回根结点
}

关于find函数还有个路径压缩的知识点：

else return find(f[x]);//递归返回，一个个找它的父结点，最终找到根节点

else return f[x]=find(f[x]);//直接将结点连到其根节点上

第二个代码优化时间的方法就叫路径压缩。

如图，求这棵树所有结点的祖先，时间复杂度取决于这棵树的深度，是O(n²)。

如图，求这棵树所有结点的祖先，时间复杂度取决于结点的个数，是O(n)。
∴路径压缩能优化时间复杂度。

join函数(合并两个结点的根结点)：

void join(int x,int y){
    f[find(x)]=find(y);//f数组用来存结点的祖先，通过find函数，合并两个结点x、y的根结点
    return;//合并后别忘了直接返回
}

判断(两个结点是否有共同根结点)：

if(find(a)==find(b))
    cout<<"Y"<<endl;//如果结点a和b有相同的根结点，则输出“Y”
else
    cout<<"N"<<endl;//否则输出“N”

———————————————————————————————————————————————————————
【模板】
(注释版)

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],a,b,c;//数组f[i]记录i的根结点
int find(int x){
    if(f[x]==x) return x;//如果结点本身就是根结点，直接返回自己
    else return f[x]=find(f[x]);//否则通过路径压缩递归返回根结点
}
void join(int x,int y){
    f[find(x)]=find(y);//通过find函数，合并两个结点x、y的根结点
    return;//合并后别忘了直接返回
}
int main(){//好习惯，直接从主函数读起
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;//初始化根结点数组，确保每个结点现在的根结点都是自己
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(a==1)//a为1时进行合并操作
            join(b,c);//直接调用join()函数
        else
            if(find(b)==find(c))//当结点b、c的根结点相等时，则它们在一个集合里
                cout<<"Y"<<endl;
            else//否则它们不属于同一个集合
                cout<<"N"<<endl;
    }
    return 0;
}

(无注释版)

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],a,b,c;
int find(int x){
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
void join(int x,int y){
    f[find(x)]=find(y);
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(a==1)
            join(b,c);
        else
            if(find(b)==find(c))
                cout<<"Y"<<endl;
            else
                cout<<"N"<<endl;
    }
    return 0;
}

———————————————————————————————————————————————————————
总结
并查集分3步：
1. 把每个结点所在的集合初始化为它自己
2. 将两个不同集合的结点合并(join函数)
3. 查找结点所在集合的根结点(find函数)
———————————————————————————————————————————————————————
经典例题:
P3367
题目
题解