A1021 Deepest Root (25 point(s))

DFS求最深叶结点

1. 原文

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:

5
1 2
1 3
1 4
2 5

Sample output 1:

3
4
5

Sample Input 2:

5
1 3
1 4
2 5
3 4

Sample output 2:

Error: 2 components

2. 解析

连通图：从一个点开始遍历整个图，同时记录visit[root]=true，最终visit[root]==false的个数就是连通分量的个数

最深叶结点：先取得从根开始的最深叶结点，再以最深叶结点为根遍历，得最深叶结点

3. AC代码

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
vector<int> v[10010];
bool visit[10010]={false};
set<int> s;
vector<int> ans;
int maxdeep=-1;
void dfs(int root,int deep)
{
	//printf("%d\n", root);
	visit[root]=true;
	if (deep>maxdeep)
	{
		maxdeep=deep;
		ans.clear();
		ans.push_back(root);
	}else if (deep==maxdeep){
		ans.push_back(root);
	}
	if (v[root].size()==0)
	{
		return;
	}
	for (int i = 0; i < v[root].size(); ++i)
	{
		if (visit[v[root][i]]==false)
		{
			dfs(v[root][i],deep+1);
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	int a,b;
	for (int i = 0; i < n-1; ++i)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int cnt=0; int start=0;
	for (int i = 1; i <= n; ++i)
	{
		if (visit[i]==false)
		{
			dfs(i,1);
			cnt++;
			if (ans.size()!=0)
			{
				start=ans[0];
			}
			for (int j = 0; j < ans.size(); ++j)
			{
				s.insert(ans[j]);
			}      
		}
	}
	if (cnt<2)
	{
		maxdeep=-1;
		fill(visit,visit+10010,false);
		dfs(start,1);
		for (int i = 0; i < ans.size(); ++i)
		{
			s.insert(ans[i]);
		}
		for (set<int>::iterator i = s.begin(); i != s.end() ; ++i)
		{
			printf("%d\n",*i);
		}
	}else{
		printf("Error: %d components\n",cnt);
	}
	return 0;
}