PAT甲级1021. Deepest Root
题意：
连接和非循环的图可以被认为是一棵树。树的高度取决于所选的根。现在你应该找到导致最高树的根。这样的根称为最深根。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，
第一行包含正整数N（<= 10000），它是节点的数量，因此节点从1到N编号。然后按N-1行，每个都通过给定两个相邻节点的数字来描述一个边。
输出规格：
对于每个测试用例，打印一行中最深的根。如果这样的根不是唯一的，
打印他们的数字增加的顺序。在给定的图形不是树的情况下，打印“错误：K组件”，其中K是图中连接的组件的数量。
思路：
我先用并查集看是不是树。然后任意点dfs，然后从得到的最远点为起始点再次dfs，这样直径两段的点就都可以得到了。然后在set里输出也可以。
- 测试点2：这里我卡了好久。是输出有几个连通分量。我循环的时候if(count > 1)直接break了。。害我一直错 = =。测试点2就是好多个连通分量。这里地方卡住可以说是十分rz了。
- 边的储存，因为题目限制65536kb,如果直接用数组int[10000][10000]至少用了800000000/1024 = 781 250kb所以不能直接用数组，可以用vector或者map动态储存
ac代码：
C++
// pat1021.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<unordered_map>
using namespace std;
unordered_map<int, vector<int>> map;
int pre[10005];
int n;
vector<int> hh;
bool visit[10005];
int mosth;
vector<int> res;
void findhighest(int height,int cur,vector<int>& h)
{
if (height > mosth)
{
mosth = height;
h.clear();
h.push_back(cur);
}
else if (height == mosth)
{
h.push_back(cur);
}
visit[cur] = true;
for (int i = 0; i < map[cur].size(); i++)
{
if (!visit[map[cur][i]])
{
findhighest(height + 1, map[cur][i], h);
visit[map[cur][i]] = false;
}
}
}
int findparent(int x)
{
return pre[x] == x ? pre[x] : findparent(pre[x]);
}
void merge(int x, int y)
{
int xx = findparent(x);
int yy = findparent(y);
if (xx == yy) return;
pre[yy] = xx;
}
int main()
{
memset(visit, false, sizeof(visit));
mosth = -1;
cin >> n;
for (int i = 1; i <= n; i++)
pre[i] = i;
int n1, n2;
for (int i = 1; i < n; i++)
{
cin >> n1 >> n2;
map[n1].push_back(n2);
map[n2].push_back(n1);
merge(n1, n2);
}
int count = 0;
for (int i = 1; i <= n; i++)
{
if (pre[i] == i) count++;
}
if (count > 1) cout << "Error: " << count << " components" << endl;
else
{
findhighest(0, 1, hh);
mosth = -1;
memset(visit, false, sizeof(visit));
findhighest(0, hh[0], res);
for (int i = 0; i < hh.size(); i++)
{
res.push_back(hh[i]);
}
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << endl;
while (i + 1 < res.size() && res[i] == res[i + 1]) i++;
}
}
return 0;
}