首页 > 其他 > 详细

P1551 亲戚 【并查集】

时间:2020-06-28 21:17:36      阅读:65      评论:0      收藏:0      [点我收藏+]

题目

https://www.luogu.com.cn/problem/P1551

技术分享图片

 

 思路

使用并查集进行关系的记录

注意father函数的初始化!!!

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int father[6000], ranks[6000];
int find(int x)
{
    if (father[x] == x)return x;
    return father[x] = find(father[x]);
}
void merge(int x,int y)
{
    int a = find(x);
    int b = find(y);
    if (a==b)return;
    if (ranks[a] > ranks[b])father[b] = a;
    else
    {
        father[a] = b;
        if (ranks[a] == ranks[b])ranks[b]++;
    }
}

int main()
{
    int n, m, p;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 0; i <= n; i++)father[i] = i;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    for (int i = 0; i < p; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (find(a) == find(b))printf("Yes\n");
        else printf("No\n");
    }

}

 

P1551 亲戚 【并查集】

原文:https://www.cnblogs.com/Jason66661010/p/13204985.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!