美文网首页
2020-06-25 亲戚

2020-06-25 亲戚

作者: JalorOo | 来源:发表于2020-06-25 22:48 被阅读0次

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

知识点:

  • 并查集
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>

#define SIZE 10005
using namespace std;

int read(){
    int x = 0, f =1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10 + c - '0';
        c = getchar();
    }
    return x*f;
}

int f[SIZE];
int FindDad(int x)//找出x家的大佬 也就是二叉树的祖先节点
{
    if(f[x]==x)//x是x的爸爸,简单的来说就是x没爸爸了
    //他是家里最大的大佬,所以返回的x就是我们所求的祖先节点
        return x;

    return  f[x] = FindDad(f[x]);//x不是他自己的爸爸,所以他上面还
    //有爸爸,我们的目标是祖先节点,所以我们此时要做的是问他
    //爸爸的爸爸是谁,即再使用一次fd(find)函数【其实就是一个递归过程
}

void Link(int x,int y)
{
    f[FindDad(y)]=FindDad(x);//合并x子集和y子集,直接把x子集的祖先节
    //点与y子集的祖先节点连接起来,通俗点来说就是把x的最大祖
    //先变成y子集最大祖先的爸爸
}

int main(){
    int n = read(), m = read(),p = read();
    
    for (int i = 1; i<=n; i++) {
        f[i] = i;
    }
    
    for (int i = 0; i<m; i++) {
        int Mi = read(),Mj = read();
        Link(Mi, Mj);
    }
    
    for (int i = 0; i<p; i++) {
        int Pi = read(),Pj = read();
        if (FindDad(Pi)==FindDad(Pj)) {
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}


相关文章

网友评论

      本文标题:2020-06-25 亲戚

      本文链接:https://www.haomeiwen.com/subject/kabefktx.html