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，解题过程

姥姥太好了，这一题设计的这么直白。。。o(*￣▽￣*)ブ

一发入魂