PAT甲级1118Birds in Forest

Posted on | | Visitors:
Words count in article: 453 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805354108403712

题解

题目要求

  • 输入
    • N：正整数，不超过1000，照片的数量
    • N张照片：每张照片中有K只鸟，鸟的索引从1开始，不超过10000。假设一张图片中出现的所有鸟属于同一棵树
    • Q：正整数，不超过10000，查询的数量
    • Q个查询
  • 输出
    • 有多少颗树、多少只鸟
    • 判断Q对鸟是否属于同一颗树

解题思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// Problem: PAT Advanced 1118
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805354108403712
// Tags: 并查集 路径压缩

#include <iostream>
using namespace std;

const int MAXN = 10001;
int tree[MAXN];
int birdNum[MAXN];

int findTree(int x){
    return (x == -1 || x == tree[x]) ? x : tree[x] = findTree(tree[x]);
}

void UNION(int a, int b){
    int ta = findTree(a), tb = findTree(b);
    if (ta != tb)
        tree[tb] = ta;
}

int main()
{
    fill(tree, tree + MAXN, -1);
    int n, q, k, bird1, bird2;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &k);
        scanf("%d", &bird1);
        if (tree[bird1] == -1)
            tree[bird1] = bird1; // 记录该鸟
        for (int j = 1; j < k; j++){
            scanf("%d", &bird2);
            if (tree[bird2] == -1)
                tree[bird2] = bird2; // 记录该鸟
            UNION(bird1, bird2);
        }
    }

    int tempTree;
    for (int i = 0; i < MAXN; i++){
        tempTree = findTree(i);
        if (tempTree != -1){
            birdNum[tempTree] += 1;
        }
    }
    int treeCount = 0, birdCount = 0;
    for (int i = 0; i < MAXN; i++){
        if (birdNum[i] > 0){
            treeCount += 1;
            birdCount += birdNum[i];
        }
    }
    printf("%d %d\n", treeCount, birdCount);
    scanf("%d", &q);
    int tree1, tree2;
    while (q--){
        scanf("%d%d", &bird1, &bird2);
        tree1 = findTree(bird1);
        tree2 = findTree(bird2);
        if (tree1 != -1 && tree2 != -1 && tree1 == tree2)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!