朋友圈问题

并查集典型的一个例题是朋友圈问题 > A和B是朋友，B和C是朋友，那么A和C也是朋友，即朋友的朋友也是朋友

输入格式

第一行：三个整数 n,m,p(n≤5000,m≤5000,p≤5000)分别表示有n 个人，m 个朋友关系，询问p 对朋友关系。

接下来 m 行：每行两个数Ai,Bi1≤Ai,Bi≤N，表示Ai​ 和 Bi具有朋友关系。接下来 p 行：每行两个数，询问两人是否为朋友。

#include<iostream>  
#include<algorithm>  
#include<string.h>  
using namespace std;  
int mark[5005],fa[5005];  
int get(int x) // 查询父节点
{  
    if(fa[x]==x)
        return x;  
    return fa[x]=get(fa[x]);  
}  
int main()
{  
    int n,m,p;
    cin>>n>>m>>p;  
    int a,b;   
    memset(mark,0,sizeof(mark)); //初始都不是朋友
    for(int i=1;i<=n;i++)
        fa[i]=i;  //父节点设为自己
    while(m--)
    {  
        cin>>a>>b;  
        a=get(a);  
        b=get(b);  
        if(a!=b) // 不是同一个父节点
        {  
            fa[a]=b;  // 指向同一个父节点
        }  
    }  
    for(int i=1;i<=p;i++)
    {  
        cin>>a>>b;  
        a=get(a);
        b=get(b);  
        if(a==b)
            mark[i]=1;  //是朋友标记为1
    }  
    for(int i=1;i<=p;i++)
    {  
        if(mark[i])
            cout<<"Yes"<<endl;  
        else 
            cout<<"No"<<endl;  
    }  
    return 0;  
}