并查集入门-白红宇

并查集入门

阅读量：3900 次

发布时间：2019-05-23

本文共 1358 字，大约阅读时间需要 4 分钟。

以下面这道题为例来解释并查集：

题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式
输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
输入输出样例

输入样例#1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例#1：
N
Y
N
Y

#include
   
    #include
    
     #include
     
      using namespace std;//并查集的问题//需要实现两个问题，第一个是查询，一个是合并//对于查询来说：就是看这两个点的祖宗是否一样  而合并则是，将这个两个点的祖宗结点合到一起 //需要创建一个数组来记录每一个结点的祖宗结点，并将其初始化为自身    int i;    int N,M;    int z,x,y;    int a[100];    //写一个方法，判断这两个是不是同一个祖宗    bool check(int x,int y){
           if(a[x]==a[y])            return true;        else            return false;    }    //其次就是写一个方法，来让两个点和并,也就是将其中一个的祖宗变成另一个的祖宗    void merge_1(int x,int y){
           if(check(x,y)==false){
   //如果这两个确实不是同一个,那就把其中一个改成另一个，并且数组中所有的等于a[x]的值都变成a[y]            for(i=1;i<100;i++){
                   if(a[i]==a[x])                    a[i]=a[y];            }        }    }int main(){
       //输入元素数量和操作数量    scanf("%d%d",&N,&M);    for(i=1;i<=N;i++)       a[i]=i;    while(M--){
           scanf("%d%d%d",&z,&x,&y);        if(z==1)//表示是合并,这样子写会出现一些问题，就是在合并的时候，容易将原本同祖宗的值，变成不同祖宗的，所以就需要在合并的时候，将所有的值都合并            merge_1(x,y);        else if(z==2){
   //表示是判断            if(check(x,y))                printf("Y\n");            else                printf("N\n");        }    }}