PAT甲级1021Deepest Root (25 分)

思路

首先dfs求图中树的个数，接着两遍dfs求树直径上的端点，最后结果为两次dfs得到的端点的并集

题目描述

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 (≤10
4
) 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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

AC代码(C++)

#include <iostream>
#include <vector>
#include <set>
#define MAXN 10005
using namespace std;
vector<int>nodes[MAXN];
set<int>ans;
bool visited[MAXN];
int maxdepth = 0;
void dfs(int s, int d){
    if(d > maxdepth){
        maxdepth = d;
        ans.clear();
        ans.insert(s);
    }else if(maxdepth == d)ans.insert(s);
    visited[s] = true;
    for(int i = 0; i < nodes[s].size(); i++)
        if(!visited[nodes[s][i]])
            dfs(nodes[s][i], d + 1);
}
int main(int argc, const char * argv[]) {
    int n, n1, n2, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++){
        scanf("%d%d", &n1, &n2);
        nodes[n1].push_back(n2);
        nodes[n2].push_back(n1);
    }
    for(int i = 1; i <= n; i++)
        if(visited[i] == false){
            dfs(i, 0);
            cnt++;
        }
    if(cnt > 1){printf("Error: %d components\n", cnt);return 0;}
    fill(visited, visited + n + 1, 0);
    set<int>tep = ans;
    dfs(*ans.begin(), 0);
    for(auto it = tep.begin(); it != tep.end(); it++){
        ans.insert(*it);
    }
    for(auto it = ans.begin(); it != ans.end(); it++){
        printf("%d\n", *it);
    }
    return 0;
}