洛谷P1551 亲戚(并查集)

  • 时间:
  • 来源:互联网
  • 文章标签:

题目链接
思路:
并查集的模板题目
关于并查集相关知识可以看此博客
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;
}

本文链接http://www.taodudu.cc/news/show-1782139.html