C++——树的统计（附毒瘤数据）

题目描述

输入森林中的节点关系，统计森林中树的数量，输出树的根。

输入格式

第1行：输入两个整数n, k

第2~k+1行：每行两个节点编号：i, j  i是j的父节点

输出格式

第一行：树的数量

第二行：依次输出森林中树的根节点编（从小到大）

样例

输入：

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

输出：

2
7 9

数据范围与提示：

n<=100
k<=100
i<=100
j<=100

（毒瘤数据）

63 12
61 22
46 43
48 94
49 27
28 70
95 70
45 45
36 26
84 61
77 81
22 57
12 97

数据很烦，有形成环的，甚至有越界的（一共一百个测试点）

第一次用并查集得了74分，后来猛然发现这是一道思维题——只要在范围内的某个点不是另一个点的子结点，那么TA一定就是根节点！！！

第二次，可惜数据太毒瘤，只得了85分……

第三次，不成功便成仁，AC！~~~

AC Code：

#include <bits/stdc++.h>
#define Maxn 105
using namespace std;
int n, k, a, s, b, x[Maxn];
bool p[Maxn];
int main() {
    scanf("%d %d", &n, &k);
    n = abs(n);
    k = abs(k);
    for (int i = 1; i <= k; i++) {
        scanf("%d %d", &a, &b);
        a = abs(a);
        b = abs(b);
        p[b] = (a != 0);
    }
    for (int i = 1; i <= n; i++)
        if (!p[i])
            x[++s] = i;
    printf("%dn", s);
    for (int i = 1; i <= s; i++) printf("%d ", x[i]);
    return 0;
}

最后

以上就是甜蜜蜡烛为你收集整理的C++——树的统计（附毒瘤数据）的全部内容，希望文章能够帮你解决C++——树的统计（附毒瘤数据）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。