蒟蒻学习并查集笔记

佚名 6年前 (2019-04-14) 随笔 1379人围观抢沙发百度已收录

并查集核心：
找母点(也可称作原始点，具有fa[i]=i的特征;)
首先母点初始化，即fa[i]=i;
后面对于输入的数据的处理:
对x,y找各自的母点:此处推荐递归(详见代码);
判断：如果母点相同，那么不用做操作，因为本来就在一个集里面orz;
如果不相同，那么把x的母点变成y:因为输入数据表示x，y为一个集中；
基本结束；
见代码

 1 int find(int x)//返回最原始母点
 2 {
 3     if(x==fa[x]) return x;
 4     return fa[x]=find(fa[x])
 5 }
 6 void merge(int x,int y)//并成一个母点
 7 {
 8     int fx=find(x);
 9     int fy=find(y);
10     if(fx!=fy) fa[fx]=fy;
11 }//原始母点有个特点:fa[i]=i;原始母点的数量就表示有多少个集.

附上一篇洛谷题解:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

P3367

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int fa[maxn];
int find(int x)//找母点
{
  if(fa[x]==x) return x;
  return fa[x]=find(fa[x]);
}
void m2(int x,int y)//进行结果的输出
{
  int fx=find(x);int fy=find(y);
  if(fx!=fy)
    printf("N\n");
  else printf("Y\n");
}
int main()
{
  int z,x,y;
  int m,n;scanf("%d%d",&m,&n);
  for(int i=1;i<=m;i++) fa[i]=i;//母点的初始化
  for(int i=1;i<=n;i++)
    {
      scanf("%d%d%d",&z,&x,&y);//输入数据
      if(z==1) fa[find(x)]=find(y);//完成并的操作
      else m2(x,y);
    }
}