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
#include<cstdio>#include<vector>#include<set>#include<algorithm>using namespace std;const int maxn = 10000;vector<int> G[maxn];bool  vis[maxn] = {false};int maxdepth = 0;int N;set<int> deepestroots;void DFS(int u, int depth){	if (maxdepth < depth)	{		maxdepth = depth;		deepestroots.clear();		deepestroots.insert(u + 1);	}	else if (maxdepth == depth)	{		deepestroots.insert(u + 1);	}	vis[u] = true;	for (int i = 0; i < G[u].size(); i++)	{		int t = G[u][i];		if (!vis[t])		{			DFS(t, depth + 1);		}	}}void DFSTrave(vector<int>*G){	int count = 0;	for (int i = 0; i < N; i++)	{		if (!vis[i])		{			DFS(i, 1);			count++;		}	}	if (count == 1)	{		set<int>::iterator it = deepestroots.begin();		int s = *(it)-1;		maxdepth = 0;		fill(vis, vis + maxn, false);		set<int> deepestrootstemp = deepestroots;		deepestroots.clear();		DFS(s, 1);		it = deepestrootstemp.begin();		for (it; it != deepestrootstemp.end(); it++)		{			deepestroots.insert(*(it));		}		it = deepestroots.begin();		for (it; it != deepestroots.end(); it++)		{			printf("%d/n", *it);		}	}	else	{		printf("Error: %d components/n", count);	}}//只需至少两次DFS就行，若太多会超时，第一次DFS找出深度最大的那些点，然后从中任选一个进行//第二次DFS，再次找深度最大的哪些点，这两次DFS所找到的点的并集就是，注意去重和排序int main(){	scanf("%d", &N);	int u, v;	if (N == 1)	{		printf("1/n");		return 0;	}	for (int i = 0; i < N - 1; i++)	{		scanf("%d %d", &u, &v);		G[u - 1].push_back(v - 1);		G[v - 1].push_back(u - 1);	}	DFSTrave(G);	return 0;}