1021 Deepest Root
分数 25
作者 CHEN, Yue
单位 浙江大学
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
* 总体思路是：先判断该图是不是一棵树，可以用 Floodfill漫水填充法来判断；
*
* 如果不是一棵树，可以用Floodfill漫水填充法来算出连通块的数量；
* 如果是一棵树，那么用叶子节点作为树根，树的深度是最深的(关键），由于有多个节点作为
* 树根的时候，同时拥有最大深度，所以还要把叶子节点进行遍历一遍，求出所有拥有最大深度
* 的树根结点编号。
*
* 由于树是双向边，所以叶子结点可以用一个degree数组来求出，当编号值为1的时候，则
* 该编号是叶子节点，但要注意节点数目是一的时候，此时叶子结点为1，根结点也为1，但
* 是degree[1] = 0,所以树的节点数目为1的时候，需要特判一下；
*
* 最后就是求结点深度的一个函数，具体操作详看代码！
/**
* 总体思路是：先判断该图是不是一棵树，可以用 Floodfill漫水填充法来判断；
*
* 如果不是一棵树，可以用Floodfill漫水填充法来算出连通块的数量；
* 如果是一棵树，那么用叶子节点作为树根，树的深度是最深的(关键），由于有多个节点作为
* 树根的时候，同时拥有最大深度，所以还要把叶子节点进行遍历一遍，求出所有拥有最大深度
* 的树根结点编号。
*
* 由于树是双向边，所以叶子结点可以用一个degree数组来求出，当编号值为1的时候，则
* 该编号是叶子节点，但要注意节点数目是一的时候，此时叶子结点为1，根结点也为1，但
* 是degree[1] = 0,所以树的节点数目为1的时候，需要特判一下；
*
* 最后就是求结点深度的一个函数，具体操作详看代码！
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4+10;
vector<int> Adj[N];
//degree存储每个节点的出度和入度之和
int degree[N], hs[N];
int Nv ; //顶点数
void Read()
{
cin >> Nv;
for(int i=1; i<Nv; ++i)
{
int u,v;
cin >> u >> v;
//顶点度数加1
degree[u]++;
degree[v]++;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
}
void dfs(int u, int c)
{
hs[u] = c;
for(int i=0; i< Adj[u].size(); ++i)
{
int v = Adj[u][i];
if(hs[v] == 0)
dfs(v, c);
}
}
int is_traver()
{
int c = 0;
//Floodfill漫水填充法，也称为种子填充法；
for(int u=1; u<=Nv; ++u)
if(hs[u] == 0)
{
--c;
dfs(u, c);
}
//以下代码根本不需要，直接返回 -c 即可，实现的效果一样
int minval = 0;
for(int i=1; i<=Nv; ++i)
minval = min(minval, hs[i]);
return -minval;
}
//求以结点u为根节点的树的最大深度
int get_depth(int u)
{
hs[u] = 1;
int maxdepth = 0;
for(int i=0; i<Adj[u].size(); ++i)
{
int v = Adj[u][i];
if(hs[v] == 0)
maxdepth = max(maxdepth, get_depth(v) + 1);
//根节点的高度等于子节点的高度+1
}
return maxdepth;
}
void Deal()
{
vector<int> chi;
for(int i=1; i<=Nv; ++i)
if(degree[i] == 1) //求出叶子节点
chi.push_back(i);
//pq元素的第一个值表示根节点的高度，第二个值表示节点编号
priority_queue<PII> pq;
for(int i=0; i<chi.size(); ++i)
{
fill(hs, hs+N, 0); //求每个叶子节点的高度的时候，记得把hs数组的值恢复为0
int u = chi[i];
int cnt = get_depth(u);
pq.push({cnt, u});
}
set<int> st;
PII top;
if(pq.size())
{
top = pq.top();
pq.pop();
}
//这儿可得千万小心，当节点数目只有一个的时候，答案就是1，所以得特判一下；
else
top = {1, 1};
int maxd = top.first;
st.insert(top.second);
while(pq.size())
{
PII top = pq.top();
pq.pop();
if(top.first == maxd)
st.insert(top.second);
else
break; //深度不一样，说明后面的节点编号不是最大深度结点，直接退出循环
}
for(auto s : st)
cout << s << endl;
}
int main()
{
Read();
int cnt = is_traver();
if(cnt != 1)
printf("Error: %d components\n", cnt);
else
Deal();
return 0;
}