欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

洛谷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