并查集是对集合进行查找与合并的一种数据结构
例题
luogu P1551 亲戚
时空限制
1000ms / 128MB
题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
题目描述
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。输入格式:
第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。输出格式:
P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
输入样例#1:
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6输出样例#1:
Yes
Yes
No
很容易想到建立一个图论模型,然后dfs,但是这样时间复杂度太高,并查集是可以处理这样的任务的。
定义
并查集是对集合进行查找与合并的一种数据结构,一般用树实现。
并查集的操作分为两种:合并与查询
实现
我们可以开一个数组a[n],其中a[i]表示第i个人的父节点是a[i],
一开始,我们把每个人的父节点设为他们自己,即初始化a[i] = i。这时,所有人都可以理解为一个单独的个体,现在,我们开始合并亲戚,组成“家族”。
过程
合并
我们合并1和2为亲戚,我们合并时选择让左边的数成为父节点,即a[2] = 1。
合并1和5为亲戚,1为父节点,即a[5] = 1。
合并3和4为亲戚,3为父节点,即a[4] = 3。
合并5和2为亲戚,2为父节点,但我们发现2有了父节点,我们就递归寻找2,5的祖先节点,发现是一个,不合并。
合并1和3为亲戚,1为父节点,即a[3] = 1。
查找
查找1和4,我们递归查找他们的祖先节点,同时将他们的每一个父节点和自己都直接连接他们的祖先节点(1本身就是祖先节点,所以直接返回他自己),以降低搜索复杂度(路径压缩),我们通过查找发现1,4的祖先节点是一个,输出“Yes”。
查找2和3,我们递归查找他们的祖先(因为之前我们之前路径压缩过,所以可以很容易地搜索到),发现是一个祖先,输出“Yes”。
查找5和6,我们递归查找他们的祖先,找5返回1,找6返回6,发现不是一个,输出“No”。
AC 代码
#include <cstdio>
int n, m, p, a[10001] = { 0 }; //a[i]表示i的祖先是a[i]
int find(int x)
{
if (a[x] == x) return x; //如果找到祖先,即a[x]=x(自己的祖先是自己),返回节点的值
//int a[x]的祖先 = find (a[x]);
//a[x] = a[x]的祖先;
//return a[x]的祖先;
return a[x] = find(a[x]); //递归查找祖先并更改父节点们的祖先
}
void merge(int xi, int yi) //合并xi,yi
{
int xz = find(xi), yz = find(yi); //找祖先
if (xz != yz) a[yz] = xz;
}
int main()
{
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++) a[i] = i; //初始化把每个人的父节点设为他们自己
int xi, yi;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &xi, &yi);
merge(xi, yi); //合并xi,yi
}
for (int i = 1; i <= p; i++)
{
scanf("%d%d", &xi, &yi);
if (find(xi) == find(yi)) //如果xi的祖先节点=yi的祖先节点
printf("Yes\n");
else printf("No\n");
}
return 0;
}
Comments NOTHING