PAT 甲级 1021. Deepest Root (25) C++版

Posted on Edited on In

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.

Sample Input 1:

5
1 2
1 3
1 4
2 5

Sample Output 1:

3
4
5

Sample Input 2:

5
1 3
1 4
2 5
3 4

Sample Output 2:

Error: 2 components

先用深搜判断有几个连通子图，如果不只有一个连通子图，直接输出；如果只有一个连通子图，那么就要求最深的根，最深用对每个节点进行广搜求层次的方法求得

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>

using namespace std;

vector<vector<int> > m;

int *visited, *level;

void dfs(int cur) {
    for (int i = 0; i < m[cur].size(); i++) {
        if (visited[m[cur][i]] == 0) {
            visited[m[cur][i]] = 1;
            dfs(m[cur][i]);
        }
    }
}

int getMax(int n) {
    int maxValue = level[1];
    for (int i = 2; i <= n; i++) {
        if (level[i] > maxValue) {
            maxValue = level[i];
        }
    }
    return maxValue;
}

int bfs(int cur, int n) {
    queue<int> r;
    r.push(cur);
    fill(visited, visited + n + 1, 0);
    fill(level, level + n + 1, 0);
    level[cur] = 1;
    visited[cur] = 1;
    while (r.size() != 0) {
        cur = r.front();
        r.pop();
        for (int i = 0; i < m[cur].size(); i++) {
            int c = m[cur][i];
            if (visited[c] == 0) {
                visited[c] = 1;
                r.push(c);
                level[c] = level[cur] + 1;
            }
        }
    }
    return getMax(n);
}

int main() {
    int n = 0;
    scanf("%d", &n);
    m.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        m[a].push_back(b);
        m[b].push_back(a);
    }

    int k = 0;
    visited = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            dfs(i);
            k++;
        }
    }

    if (k != 1) printf("Error: %d components\n", k);
    else {
        level = new int[n + 1];
        int maxValue = -1;
        vector<int> ans;
        for (int i = 1; i <= n; i++) {
            int v = bfs(i, n);
            if (v > maxValue) {
                ans.clear();
                ans.push_back(i);
                maxValue = v;
            } else if (v == maxValue) {
                ans.push_back(i);
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            printf("%d\n", ans[i]);
        }
    }
    delete[] level;
    delete[] visited;
    return 0;
}