1021 Deepest Root

这道题的关键在于如何求两个最远的结点,二叉树比较容易一直DFS就能找到,但是普通树就比较麻烦。要先找到一端,再去找另外一端,两端的并集就是答案。因为结点都是对称的,所以两端都是答案。还要注意去重,12 13这种就会重复。

#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
vector<int>pre[maxn];
int n;
bool vis[maxn];
vector<int>ans;
void DFS(int s)
{
int i;
vis[s] = true;
for (i =;i<pre[s].size(); i++)
{
if (vis[pre[s][i]] == false)
{
DFS(pre[s][i]);
}
}
return;
}
vector<int>temp;
int maxh = ;
void find(int s,int height)//寻找以s为根距离s最远的结点,height为s距离该节点的距离.
{
if (vis[s] == true)
return;
vis[s] = true;
if (height > maxh)
{
temp.clear();
temp.push_back(s);
maxh = height;
}
else if (height == maxh)
{
temp.push_back(s);
}
int i;
for (i = ; i < pre[s].size(); i++)
{
find(pre[s][i], height + );
}
}
int main()
{
scanf("%d", &n);
int i, j;
for (i = ; i <= n-; i++)
{
int st, ed;
scanf("%d %d", &st,&ed);
pre[st].push_back(ed);
pre[ed].push_back(st);
}
memset(vis, false, sizeof(vis));
int sum = ;
for (i = ; i <= n; i++)
{
if (vis[i] == false)
{
sum++;
DFS(i);
}
}
if (sum >=)
{
printf("Error: %d components\n", sum);
}
else if (n == )
{
printf("%d\n", );
}
else
{
memset(vis, false, sizeof(vis));
find(, );//此时temp里面已经装了若干边缘结点
ans = temp;
memset(vis, false, sizeof(vis));
maxh = ;
temp.clear();
find(ans[], );
for (i = ; i < temp.size(); i++)
{
ans.push_back(temp[i]);
}
sort(ans.begin(), ans.end());
printf("%d\n", ans[]);
for (i = ; i <ans.size(); i++)
{
if(ans[i]!=ans[i-])
printf("%d\n",ans[i]);
}
}
}
上一篇:Java 强制类型转换(类转换注意事项)


下一篇:nose测试中修改nose_html_reporting插件,使生成的html报告加入显示截图功能