题目描述

给出n个人的关系，然后求其中的两个有没有亲戚关系

思路

就是一个并差集

#include 
int p[100000],r[100000];
int find(int x)
{
    if (!p[x])
        return x;
    p[x]=find(p[x]);
    return p[x];
}
int insert(int x,int y)
{
    int u=find(x),v=find(y);
    if (r[u]<=r[v])
    {
        p[u]=v;
        if (r[u]==r[v]) r[v]++;
    }
    else p[v]=u;
}
int main()
{
    int n,m,l;
    scanf("%d%d%d",&l,&n,&m);
    for (int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if (find(x)!=find(y))
            insert(x,y);
    }
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if (find(x)==find(y))
            printf("Yes\n");
        else printf("No\n");
    }

}