题目链接
题目大意
description
给出n个节点标号为1-n，给出n-1条边，让你判断是不是树，如果是的话，升序输出作为根节点时可以达到最大树高的节点，如果不是的话，输出联通块数量。
思路
inspration
用并查集计算联通块数量，如果连通块只有1块那么就是一棵树，否则可以直接输出连通块数量。如果这是一颗树，bfs两次，把每次深度最大的节点扔到set里面，然后把set里的数输出就好。
坑点
pit
刚开始我觉得输出的点是叶节点就可以了，打好交了一发有两个case过不了。想了一下估计n=1的时候没考虑到，加了个特判交了一发，过了1个case，但是主要的case过不了。搜题解时发现这是求树上最长链。。。有点犯傻了。敲好交一发顺利AC。
代码
括号换行，又臭又长
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int pre[10002],hight[10002],vis[10002];
set<int>st,out;
queue<int>q;
vector<int>vec[10002];
int find(int now)
{
int temp = now,k;
while(pre[now]!=now)
{
now=pre[now];
}
while(pre[temp]!=now)
{
k=temp;
temp=pre[temp];
pre[k]=now;
}
return now;
}
void join(int a,int b)
{
pre[find(a)]=find(b);
}
int main()
{
int n,maxn=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
pre[i]=i;
hight[i]=0;
vis[i]=0;
}
for(int i=0;i<n-1;i++)
{
int from,to;
scanf("%d%d",&from,&to);
vec[from].push_back(to);
vec[to].push_back(from);
join(from,to);
}
for(int i=1;i<=n;i++)
st.insert(find(i));
if(st.size()!=1)
printf("Error: %d components\n",st.size());
else
{
q.push(1);vis[1]=1;
while(!q.empty())
{
int temp = q.front();
q.pop();
maxn=max(maxn,hight[temp]);
for(int i=0;i<vec[temp].size();i++)
if(!vis[vec[temp][i]])
{
hight[vec[temp][i]]=hight[temp]+1;
q.push(vec[temp][i]);
vis[vec[temp][i]]=1;
}
}
int flag;
for(int i=1;i<=n;i++)
if(hight[i]==maxn)
{
out.insert(i);
flag=i;
}
for(int i=1;i<=n;i++)
{
hight[i]=0;
vis[i]=0;
}
maxn=0;
q.push(flag);vis[flag]=1;
while(!q.empty())
{
int temp = q.front();
q.pop();
maxn=max(maxn,hight[temp]);
for(int i=0;i<vec[temp].size();i++)
if(!vis[vec[temp][i]])
{
hight[vec[temp][i]]=hight[temp]+1;
q.push(vec[temp][i]);
vis[vec[temp][i]]=1;
}
}
for(int i=1;i<=n;i++)
if(hight[i]==maxn)
out.insert(i);
set<int>::iterator it;
for(it=out.begin();it!=out.end();it++)
{
printf("%d\n",*it);
}
}
return 0;
}
