Luogu [P3367] 模板 并查集

【模板】并查集

 

题目详见：[【P3367】【模板】并查集] (https://www.luogu.org/problemnew/show/P3367)

这是一道裸的并查集题目（要不然叫模板呢） 废话不多说进入正题：

并查集通过一个一维数组来实现，本质上是维护一个森林。刚开始的时候，森林里的每一个结点都是一个集合（也就是只有一个结点的树），之后根据题意，逐渐将一个个集合合并（也就是合并成一棵大树）。之后寻找时不断查找父节点，当查找到父结点为本身的结点时，这个结点就是祖宗结点。合并则是寻找这两个结点的祖宗结点，如果这两个结点不相同，则任意将其中一边的集合作为另一边集合的子集。

 

AC代码：

#include<iostream>
using namespace std;
int n/*n个元素*/,m/*m个操作*/,f[10001]/*第i个人的祖宗为f[i]*/;
int find(int x)            //找祖宗（※※重点） 
{
    if(f[x]==x)            //若自己的祖宗为自己 
      return f[x];          
    else                     
      return f[x]=find(f[x]);//路径压缩（※※难点）：把递归过程中遇到的结点的祖宗结点也直接修改了 
}
void hebing(int x,int y)       //合并操作
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)                 //（其实这一步可有可无，因为之前已经判断过了） 
      f[fx]=fy;                //x的祖宗  的父亲  为y的祖宗 
    return;
} 
int main()
{
    cin>>n>>m;    //读入
    for(int i=1;i<=n;i++)
    f[i]=i;                //初始化：n个数，每个数祖宗为自己 
    for(int i=1;i<=m;i++)  //依次读入m个操作要求
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==2)           //执行查询操作 
        {
            if(find(x)==find(y)) //如果两个人为同一个祖宗，则在一个集合 （※※重点）
              cout<<"Y"<<endl;
            else           //否则不在一个集合 
              cout<<"N"<<endl;
        }
        else               //执行合并操作 
          hebing(x,y); 
    } 
    return 0;
}