PAT 甲级 刷题日记|A 1021 Deepest Root

单词积累

acyclic 非循环的 非周期的

connected components 连通分量

题目

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 (≤104) 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

思路

第一个问题：判断是否为树。由于题目已经表明，只有N-1条边，所以必然是树，或者是带环路的的森林，这样问题就转换为判断连通块的个数。
第二个问题就是计算最大深度的问题，可以逐个点开始遍历，遍历过程中记录最大深度。最后排序输出。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10003;
vector<vector<int>> gra;
int visit[maxn];
int depth[maxn];
int n;

struct node{
    int depth;
    int id;
}Node[maxn];

int dfs(int root, int depth) {
    int de = depth;
    visit[root] = 1;
    for (int i = 0; i < gra[root].size(); i++) {
        if (visit[gra[root][i]] == 0) {
            de = max(dfs(gra[root][i], depth + 1), de);
        }
    }
    return de;
}

int dfstra() {
    int times = 0;
    for (int i = 0; i <= n; i++) {
        visit[i] = 0; 
    } 
    for (int i = 1; i <= n; i++) {
        if (visit[i] == 0) {
            times++;
            dfs(i, 0);
        }
    }
    return times;
}

void dfstra2() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            visit[j] = 0; 
        } 
        Node[i].depth = dfs(i,0);
        Node[i].id = i;
        
    }
}

bool cmp(node a, node b) {
    if (a.depth != b.depth) return a.depth > b.depth;
    return a.id < b.id;
}

int main() {
    int a, b;
    cin>>n;
    gra.resize(n+1);
    for (int i = 0; i < n - 1; i++) {
        cin>>a>>b;
        gra[a].push_back(b);
        gra[b].push_back(a);
    }
    int times = dfstra();
    if (times > 1) {
        printf("Error: %d components\n", times);
    } else {
        dfstra2();
        sort(Node + 1, Node + n + 1, cmp);
        for (int i = 1; i <= n; i++) {
            if (i != 1 && Node[i].depth != Node[i-1].depth) break;
            cout<<Node[i].id<<endl;
        }
    }
}