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;}