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

迈不过友情╰ 2024-05-08 06:02 75阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

题目大意：在同一张照片里的鸟属于一个树，所以用并查集就可以做了；  
至于鸟的数量，可以通过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;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805354108403712