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.
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 思路 二次dfs
1.第一次dfs确定图是否连通，如果连通找到最深的那个点first（多个就取最先被找到的），没有输出题目要求的错误信息。
2.第二次dfs重置所有状态，然后从first开始dfs，找到的所有的最深的点即是题目要求的节点，依次插入一个set容器中（每次插入会自动排序）。 3.输出set中的所有元素就行。 代码
#include<iostream>
#include<vector>
#include<set>
using namespace std;
vector<vector<int>> graph;
vector<int> highestNodes;
vector<bool> visits(10005,false);
int maxheight = 1;
set<int> results; void dfs(int root,int height)
{
visits[root] = true;
if(height >= maxheight)
{
if(height > maxheight)
{
highestNodes.clear();
maxheight = height;
}
highestNodes.push_back(root);
}
for(int i = 0;i < graph[root].size();i++)
{
if(!visits[graph[root][i]])
dfs(graph[root][i],height + 1);
}
} inline void resetVisits(const int n)
{
for(int i = 0;i <= n;i++)
visits[i] = false;
} int main()
{
int N;
while(cin >> N)
{
//input
graph.resize(N + 1);
for(int i = 1;i < N;i++)
{
int a,b;
cin >> a >> b;
graph[b].push_back(a);
graph[a].push_back(b);
} int cnt = 0;
//handle
int first = -1; //最高的节点之一
for(int i = 1;i <= N;i++)
{
if(!visits[i])
{
cnt++;
dfs(i,1);
if( i == 1)
{
for(int j = 0;j < highestNodes.size();j++)
{
results.insert(highestNodes[j]);
if(j == 0)
first = highestNodes[j];
}
}
}
} if(cnt > 1)
cout << "Error: "<< cnt <<" components" << endl;
else
{
highestNodes.clear();
maxheight = 1;
resetVisits(N);
dfs(first,1);
for(int i = 0;i < highestNodes.size();i++ )
results.insert(highestNodes[i]);
for(auto it = results.begin();it != results.end();it++)
cout << *it << endl;
}
}
}