洛谷P1551 亲戚(并查集)
程序员文章站
2022-03-27 16:04:57
题目链接思路:并查集的模板题目关于并查集相关知识可以看此博客AC代码#include#include#includeusing namespace std;const int MAXN=5005;int fa[MAXN],rank[MAXN];inline void init(int n)//初始化{ for(int i=0;i
题目链接
思路:
并查集的模板题目
关于并查集相关知识可以看此博客
AC代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=5005;
int fa[MAXN],rank[MAXN];
inline void init(int n)//初始化
{
for(int i=0;i<n;i++)
{
fa[i]=i;
rank[i]=1;
}
}
int find(int x)//找父亲
{
return (x==fa[x])?(x):(fa[x]=find(fa[x]));
}
inline void merge(int i,int j)//合并
{
int x=find(i),y=find(j);
if(rank[x]<=rank[y])
fa[x]=y;
else
fa[y]=x;
if(rank[x]==rank[y]&&x!=y)//rank相同的两个合并秩会+1
rank[y]++;
}
int main()
{
int n,m,p,x,y;
scanf("%d %d %d",&n,&m,&p);
init(n);
for(int i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
merge(x,y);
}
for(int i=0;i<p;i++)
{
scanf("%d %d",&x,&y);
printf("%s\n",(find(x)==find(y)?"Yes":"No"));
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_44063734/article/details/109260432
上一篇: 浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛(同步赛)训练记录
下一篇: 猜拳游戏