【模板】并查集

打开Luogu搜索模板排序……除了快排第一个是并查集

于是我们就愉快的复习并查集了

还是挺简单的嘛

首先每个数一个集合,这个集合的爸爸是他自己

定义一个递归找祖宗的函数。这里就是一个路径压缩的操作,找到祖宗以后直接把自己挂到祖宗下面,把祖宗当成爸爸(祖宗成了所有人的爸爸)

合并两个集合A、B的时候,找出A和B集合的爸爸,把其中一个的爸爸挂到另一个的爸爸下面,两个集合就合并完成啦

查询a、b是否在一个集合,就找出A、B集合的爸爸看看是不是同一个,如果是就是一个集合内,不然就不是

emm,这篇文章很详细,可以看看

上代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 10005
using namespace std;
int n,m,z,x,y;
int f[MAXN];

inline void getnum(int &num)
{
num=0;
char c=getchar();
while (!isdigit(c))
c=getchar();
while (isdigit(c))
{
num=(num<<3)+(num<<1)+(c&15);
c=getchar();
}
return;
}

inline int find(int a)
{
if (f[a]==a)
return a;
else
{
f[a]=find(f[a]);
return f[a];
}
}

inline int query(int a,int b)
{
register int fa=find(a),fb=find(b);
return fa==fb;
}

inline void combine(int a,int b)
{
register int fa=find(a),fb=find(b);
if (fa!=fb)
f[fa]=fb;
return;
}

int main()
{
getnum(n),getnum(m);
for (register int i=1;i<=n;++i)
f[i]=i;
for (register int i=1;i<=m;++i)
{
getnum(z),getnum(x),getnum(y);
if (z==1)
{
combine(x,y);
continue;
}
else
{
printf("%s\n",query(x,y)?"Y":"N");
continue;
}
}
return 0;
}
-------------本文结束,感谢阅读-------------
0%