1021 Deepest Root （25 分)

2019-03-11

1021 Deepest Root （25 分)

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:

Sample Output 1:

1
2
3

3
4
5

Sample Input 2:

Sample Output 2:

1	Error: 2 components

作者: CHEN, Yue

单位: 浙江大学

时间限制: 2000 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

一个连通无环图可以看作一棵树，问哪些结点作为根时，此树的深度最大。如果图不连通，输出连通分量数。

分析

先从一个点开始dfs，计算连通分量数，并记录最大深度的结点入temp。如果为1，则从深度最大点中一点开始dfs，得到深度最大点res，加上原来temp中点，即为所求点。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>

using namespace std;
int n,a,b;
int c=0;
int visit[10010]={};
vector<vector<int>> e;
vector<int> temp;
set<int> res;
int maxd=-1;

void dfs(int i,int d){
    visit[i]=1;
    if(d>maxd){
        temp.clear();
        temp.push_back(i);
        maxd=d;
    }
    else if(d==maxd){
        temp.push_back(i);
    }
    for(int j=0;j<e[i].size();j++){
        if(!visit[e[i][j]])
            dfs(e[i][j],d+1);
    }

    return;
}

int main() {
    int s1;
    cin>>n;
    e.resize(n+1);
    for(int i=1;i<n;i++){
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i=1;i<=n;i++) {
        if(!visit[i]) {
            dfs(i, 0);
            c++;
        }
    }

    fill(visit,visit+10010,0);
    if(c==1)
    {
        if(temp.size()!=0)
            s1=temp[0];
        for(int i=0;i<temp.size();i++)
            res.insert(temp[i]);
        fill(visit,visit+10010,0);
        maxd=-1;
        temp.clear();
        dfs(s1,0);
        for(int i=0;i<temp.size();i++)
            res.insert(temp[i]);

        for(auto i:res)
            cout<<i<<endl;
    }
    else
        cout<<"Error: "<<c<<" components";
}