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 (<=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.

51 21 31 42 5Sample Output 1:
345Sample Input 2:
51 31 42 53 4Sample Output 2:
Error: 2 components
bfs判断连通块个数进而判断是否是树再依次枚举每个节点用数组记录深度，同时记录最大深度，遍历数组输出最大深度节点(从小到大遍历输出)
#include<cstdio>#include<vector>#include<queue>#include<algorithm>using namespace std;const int maxn = 1e4 + 10;bool flag[maxn] = {false};vector<int> G[maxn];int deepestRoot = -1, dep[maxn];int dfs(int x){  if(flag[x]) return 0;  flag[x] = true;  int depRoot = 0;  for(int i = 0; i < G[x].size(); ++i){    int deep = 1;    deep += dfs(G[x][i]);    if(deep > depRoot) depRoot = deep;  }  if(depRoot > deepestRoot) deepestRoot = depRoot;  return depRoot;}void bfs(int x){         //bfs判断连通块，也可以用并查集  if(flag[x]) return ;  flag[x] = true;  queue<int> Q;  Q.push(x);  while(!Q.empty()){    int top = Q.front();    Q.pop();    for(int i = 0; i < G[top].size(); ++i){      if(!flag[G[top][i]]){        flag[G[top][i]] = true;        Q.push(G[top][i]);      }    }  }}int main(){  //freopen("1021.txt", "r", stdin);    int n, v1, v2;  scanf("%d", &n);  for(int i = 1; i < n; ++i){    scanf("%d %d", &v1, &v2);    G[v1].push_back(v2);    G[v2].push_back(v1);  }  int cycleNum = 0;  for(int i = 1; i <= n; ++i){    if(!flag[i]){      ++cycleNum;      bfs(i);    }  }  if(cycleNum <= 1){  for(int i = 1; i <= n; ++i){    fill(flag + 1, flag + n + 1, 0);    dep[i] = dfs(i);  }  for(int i = 1; i <= n; ++i){    if(deepestRoot == dep[i]){      printf("%d/n", i);    }  }  }else{    printf("Error: %d components", cycleNum);  }  //fclose(stdin);  return 0;}