题解 P2978 【[USACO10JAN]下午茶时间Tea Time】

jingyangzhi · 2019-03-27 12:41:22 · 题解

标准的并查集模板，趁题目刚出水一篇c++题解，

类似题目：P3367 【模板】并查集；

[并查集详解链接]（初学请务必先理解）(https://blog.csdn.net/qq_34594236/article/details/51834882)

好以下是AC代码：

#include <iostream>

using namespace std;
int f[1009];
int n,m,q;
int fin(int k){
if(f[k]==k)return k;
return f[k]=fin(f[k]);
}//标准的并查集函数，f[n]表示n的老大是谁
int main()
{    cin>>n>>m>>q;
    int b,l;
    for(register int i=1;i<=n;i++){
        f[i]=i;//初始化，让每个牛的刚开始只认识自己，即自己是自己的老大；
    }
    for(register int i=1;i<=m;i++){
        cin>>b>>l;
        f[fin(b)]=fin(l);使ai的老大是bi
    }
    for(register int i=1;i<=q;i++){
        cin>>b>>l;
        if(fin(b)==fin(l)){
            cout<<'Y'<<endl;
        }else{
        cout<<'N'<<endl;
        }\\判断俩牛是否认识，即是否为同一老大；
      然后因为是输入进文本中的，不用存储直接输出就行了；
    }

    return 0;
}

萌新求过~~！！