Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

PAT 1021. Deepest Root

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 (<=10000) 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

解答

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int mx = 10000 + 10;
int n, father[mx], rnk[mx];
vector<int> mp[mx];

void makeSet() { for (int i = 1; i <= n; i++) father[i] = i, rnk[i] = 0; }
int findSet(int x) { return father[x]==x ? x : father[x]=findSet(father[x]); }
int unionSet(int x, int y)
{
	x = findSet(x), y = findSet(y);
	if (x == y) return 0;
	if (rnk[x] > rnk[y]) father[y] = x;
	else father[x] = y, rnk[y] += rnk[x]==rnk[y];
	return 1;
}

int dis[mx], vs[mx];
void dfs(int x)
{
	vs[x] = 1;
	for (int i = 0; i < mp[x].size(); i++)
		if (!vs[mp[x][i]])
		{
			dis[mp[x][i]] = dis[x] + 1;
			dfs(mp[x][i]);
		}
}

int main()
{
	scanf("%d", &n);
	if (n == 1)
	{
		printf("1\n"); return 0;
	}

	makeSet();
	int cnt = n; //连通分量
	for (int i = 1, a, b; i < n; i++)
		scanf("%d%d", &a, &b), mp[a].push_back(b), mp[b].push_back(a), cnt -= unionSet(a, b);

	if (cnt != 1)
		printf("Error: %d components\n", cnt);
	else
	{
		vector<int> ans;

		memset(dis, 0, sizeof(dis));
		memset(vs, 0, sizeof(vs));
		dfs(1); //任意起点dfs一次
		int *p = max_element(dis+1, dis+n+1), id = p-dis;
		for (int i = 1; i <= n; i++) 
			if (dis[i] == *p) ans.push_back(i);

		memset(dis, 0, sizeof(dis));
		memset(vs, 0, sizeof(vs));
		dfs(id); //以上次最远节点再dfs一次
		p = max_element(dis+1, dis+n+1);
		for (int i = 1; i <= n; i++) 
			if (dis[i] == *p) ans.push_back(i);

		sort(ans.begin(), ans.end());
		printf("%d\n", ans[0]);
		for (int i = 1; i < ans.size(); i++)
			if (ans[i] != ans[i-1]) printf("%d\n", ans[i]);
	}

	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论