题解：P1551 亲戚

· · 题解

题解：P1551 亲戚

看到这种判断是否是亲戚的题，一眼并查集。

思路

用数组记录每个人的上一代是谁，就像链表一样。每次读入一组亲戚关系时，就相当于把两条链表合并，需将一条链表的表头指向另一个链表。为了节省搜索时间，直接将一条链表的表头指向另一个链表的表头，这样在搜索时直接找到表头，判断是否相同就能判断两个数（人）是否位于同一链表（为亲戚）。
因为 N≤5000，每次输入两个数时的极端情况就只用查找 5000 人，而输入最多 10^4 次，极端情况需要查找 5×10^7 次，所以不会超时。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,p;
ll f[5005];

int find(int x){
    if(f[x]==x)
        return x;
    return f[x]=find(f[x]);
}

int main(){
    for(int i=1;i<=5000;i++)
        f[i]=i;
    cin>>n>>m>>p;
    for(int i=1;i<=m;i++){
        ll a,b;
        cin>>a>>b;
        f[find(a)]=find(b);
    }
    while(p--){
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}