/ Vijos / 讨论 / 家族 /

新手并查集 一次过 ^- ^

#include <stdio.h>
int father[5010],rank[5010];
void get(int size)
{
for(int i=1;i<=size;i++)
{
father[i]=i;
rank[i]=0;
}
}
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
void union1(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx==fy) return;
if(rank[fx]>rank[fy])
father[fy]=fx;
else
{
father[fx]=fy;
rank[fx]++;
}
}
int main()
{
int n,m,p,x,y;
while(scanf("%d %d %d",&n,&m,&p)!=EOF)
{
get(n);
for(int i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
union1(x,y);
}
for(int j=0;j<p;j++)
{
scanf("%d %d",&x,&y);
if(find(x)==find(y))
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9368
已通过
3839
通过率
41%
被复制
15
上传者