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;

}