1336：【例3-1】找树根和孩子

【题目描述】
给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。

【输入】
第一行：n（结点个数≤100），m（边数≤200）。

以下m行：每行两个结点x和y，表示y是x的孩子(x,y≤1000)。

【输出】
第一行：树根：root；

第二行：孩子最多的结点max；

第三行：max的孩子（按编号由小到输出）。

【输入样例】
8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8
【输出样例】
4
2
6 7 8

分析

1. 采用双亲表示法，可参考：树的双亲表示法、孩子表示法和孩子兄弟表示法；
2. 一个par数组去存储一个结点的双亲结点；然后根节点root的双亲一定为0，所以遍历n个节点即可找到根节点；然后可以通过两层循环来枚举每个结点有多少孩子，然后存储有最多孩子的结点maxNode，然后循环遍历所有结点，看看谁的双亲是maxNode即可；
3. 还可以用一个数组去存储每个结点的出度，这样就能知道每个节点有多少个孩子了，这样当n足够大的时候，O(n)的时间复杂度不会超时；
4. 解法一参考的：三部分 数据结构 --树-1336：【例3-1】找树根和孩子，解法二参考的：信息学奥赛一本通 1336：【例3-1】找树根和孩子；

解法一 O(n^2)

#include 

using namespace std;

const int N = 105;
int n, m, root, maxNode;
int par[N];

int main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        par[b] = a;
    }
    for (int i = 1; i <= n; ++i) {
        //双亲为0的结点为根节点
        if (par[i] == 0)
            root = i;
    }
    cout << root << endl;

    //找孩子最多的结点maxNode
    int maxCnt = 0;//maxNode的孩子个数
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;//查找有多少个结点的双亲为i
        for (int j = 1; j <= n; ++j) {
            if (par[j] == i)
                cnt++;
        }
        if (cnt > maxCnt) {
            maxNode = i;
            maxCnt = cnt;
        }
    }
    cout << maxNode << endl;
    for (int i = 1; i <= n; ++i) {
        if (par[i] == maxNode)
            cout << i << " ";
    }
    return 0;
}


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

解法二 O(n)

使用一个deg数组，预处理下，来优化解法一，找一个结点有几个孩子，就可以采用用一个数组记录出度数即可；

#include 

using namespace std;

const int N = 105;
int n, m, root, maxNode;
int par[N], deg[N];

int main() {
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        par[b] = a;
    }
    for (int i = 1; i <= n; ++i) {
        //双亲为0的结点为根节点
        if (par[i] == 0)
            root = i;
        //预处理，设置双亲结点par[i]的出度
        deg[par[i]]++;
    }
    cout << root << endl;

    //找孩子最多的结点maxNode
    int maxDeg = 0;
    for (int i = 1; i <= n; ++i) {
        if (deg[i] > maxDeg) {
            maxDeg = deg[i];
            maxNode = i;
        }
    }
    cout << maxNode << endl;
    for (int i = 1; i <= n; ++i) {
        if (par[i] == maxNode)
            cout << i << " ";
    }
    return 0;
}


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