前言:

今日浅浅地玩了一下刺客信条奥赛德，总结还不错。不闹了，让我来介绍一下今天的主角并查集

$ 概述:
并查集还是很神奇的，常常地用在处理两个集合问题，例如两集合的关系。

并查集有三大核心步骤–初始化、寻找根部、合并，可以当成解题模板使用

初始化即先将每一个元素的祖宗设为自己。

1
2
for(int i;i<=n;i++)
f[i]=i;

寻找根部，找到该元素的祖宗。

1
2
3
int find(int x)
if(f[x]==x)return x ;
return f[x]=find(f[x]);//这一步为路径压缩，使得每一个元素都指向该集合的祖宗。

合并就是将两个元素或者两个集合进行合并，将一方的根节点连接到另一方的根节点，进行认祖归宗。

1
f[find(a)]=find(b);

简单地介绍了一下并查集，现在我们开始实战环节。

实战

题目：并查集

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

第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。

当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。

当 Z_i=2 时，输出 X_i 与 Y_i 是否在同一集合内，是的输出 Y ；否则输出 N 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int p[N],n,m;
void init()
{
    for(int i=1;i<=n;i++)
        p[i]=i;
}
int myFind(int x)
{
    if(p[x]!=x)p[x]=myFind(p[x]);
    return p[x];
}
void myMerge(int a,int b)
{
    p[myFind(a)]=myFind(b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b;
    int number ;
    cin>>n>>m;
    init();
    while(m--)
    {
        cin>>number>>a>>b;
        if(number==1)
            myMerge(a,b);
        if(number==2)
        {
            if(myFind(a)==myFind(b))
            {
                cout<<"Y"<<endl;
            }
            else
                cout<<"N"<<endl;
        }
    }
    return 0;
}