PAT_甲級_1118 Birds in Forest (25point(s)) (C++)【并查集】

目錄

​​1，題目描述​​

​​題目大意​​

​​輸入​​

​​輸出​​

​​2，思路​​

​​3，AC代碼​​

​​4，解題過程​​

1，題目描述

• indices：index 的複數形式之一；
• index：索引; (物價和工資等的) 指數; 标志; 名額; 表征; 量度；

Sample Input:

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7      

Sample Output:

2 10
Yes
No      

題目大意

一張照片上的鳥屬于同一棵樹，若有兩張以上的照片有相同的鳥，則這些照片上的鳥屬于同一棵樹。輸出樹最多有幾棵，鳥有幾隻，并且給出一系列查詢，判斷每次查詢中的兩隻鳥是否屬于同一棵樹。

輸入

1. 第一行：照片數目N；
2. N行：N張照片上的鳥的編号；
3. 下一行：查詢的數目K；
4. K行：K對查詢；

輸出

1. 第一行：樹的最大數目，鳥的數目；
2. 接下來K行：Yes/No；

2，思路

并查集的簡單應用。不熟悉并查集的戳這裡​​@&再見螢火蟲&【并查集【算法筆記/晴神筆記】】​​

1. 每張照片上的鳥的id進行并查集合并操作，并且記錄鳥的最大id（因為鳥的id是連續的，且從1開始，是以最大id即鳥的數目）；
2. 周遊father中每隻鳥的id，将其father[id]放入set集合tree中（自動去重），tree的size即樹的最大數目；
3. 每對查詢的id1和id2，若id1的根節點==id2的根節點（是findFather(father[id])，不是父節點）

注意判斷兩隻鳥是否在同一顆樹，使用 findFather(father[id])（根節點，不是父節點）！！！

3，AC代碼

#include<bits/stdc++.h>
using namespace std;
int father[10005];
int findFather(int x){
    if(father[x] == x)
        return x;
    father[x] = findFather(father[x]);
    return father[x];
}
void unionSet(int a, int b){
    int A = findFather(a), B = findFather(b);
    if(A != B)
        father[max(A, B)] = min(A, B);
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    iota(father, father + 10005, 0);
    int N, n, K, maxID = 0, id1, id2;
    cin>>N;
    for(int i = 0; i < N; i++){
        cin>>n>>id1;
        maxID = max(maxID, id1);
        for(int j = 1; j < n; j++){
            cin>>id2;
            maxID = max(maxID, id2);
            unionSet(id1, id2);
        }
    }
    unordered_set<int> tree;
    for(int i = 1; i <= maxID; i++){
        tree.insert(findFather(father[i])); // !!!findFather(father[i])
    }
    cout<<tree.size()<<' '<<maxID<<endl;
    cin>>K;
    for(int i = 0; i < K; i++){
        cin>>id1>>id2;
        printf("%s\n", findFather(father[id1]) == findFather(father[id2]) ? "Yes":"No"); // !!!findFather(father[i])
    }
    return 0;
}      

4，解題過程