PAT（甲级）1118 Birds in Forest (25point(s))-蒲公英云

PAT（甲级）1118 Birds in Forest (25point(s))

题目

题目链接

思路

题目大意：在同一张照片里的鸟属于一个树，所以用并查集就可以做了；
至于鸟的数量，可以通过set去重存储；

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1e4 + 10;
int father[maxn], isRoot[maxn];
set<int> birds;
int findFa(int a){
     int b = a, t;
     while(father[a] != a) a = father[a];
     while(father[b] != b){
          t = father[b];
          father[b] = a;
          b = t;
     }
     return a;
}
void myUnion(int a, int b){
     int faA = findFa(a), faB = findFa(b);
     if(faA != faB){
          father[faB] = faA;
          isRoot[faA] += isRoot[faB];
          isRoot[faB] = 0;
     }
}
int main()
{
     //初始化
     for(int i = 0; i < maxn; i ++) father[i] = i;
     fill(isRoot, isRoot + maxn, 1);
     int n, k, t, last;
     scanf("%d", &n);
     for(int i = 0; i < n; i ++){
          scanf("%d", &k);
          scanf("%d", &last);
          birds.insert(last);
          for(int j = 1; j < k; j ++){
               scanf("%d", &t);
               myUnion(last, t);
               birds.insert(t);
          }
     }
     int num = 0;
     for(int i = 1; i <= birds.size(); i ++){
          if(isRoot[i] != 0) num ++;
     }
     printf("%d %d\n", num, birds.size());
     scanf("%d", &k);
     int u, v, faA, faB;
     for(int i = 0; i < k; i ++){
          scanf("%d%d", &u, &v);
          faA = findFa(u), faB = findFa(v);
          if(faA == faB) printf("Yes\n");
          else printf("No\n");
     }
     system("pause");
     return 0;
}