PAT 甲级 A1021 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 (≤104) 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

题意：

给出n个结点，和n-1个边，问这些点和边能否构成一棵树， 如果能求这颗树的最大高度（无向图，根节点不同，其高度也不同），如果不能输出连通块的个数。

思路：
有n-1条边且连通的图一定是树，我们需要的就是遍历图所有的节点，找到连通块的个数，不止一块的话肯定不是树，如果只有一个连通块且边数是节点数减一，就肯定是树了，再遍历这个图，找到最大深度，和满足最大深度的叶子结点，将其放到temp里面，这些就是满足最大深度的根节点编号，但是并不是最终答案，最终答案需要再以temp中随机的一个根节点作为开始，反向再遍历这个图，将满足条件的结点再放到temp里面，这个才是最终的答案，意思就是正向要遍历一次，满足条件的结点作为根节点再遍历一次。

代码：
 

//并查集遍历图找出连通块，判断是否为树; 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 10010;
int father[maxn] = {0};
bool vis[maxn] = {false};
vector<int > node[maxn];
int n; 
//并查集三件套;
 
void init() {//初始化 
	for(int i = 1; i <= n ;i++) {
		vis[i] = false;
		father[i] = i;	
	}
	return ;
}

int findRoot(int x) {
	if(x == father[x]) return x;
	else {//路径压缩; 
		int root = findRoot(father[x]);
		father[x] = root;
		return root;
	}
}

void Union(int a, int b) {
	int rootA = findRoot(a);
	int rootB = findRoot(b);
	if(rootA != rootB) {
		father[rootB] = rootA;
	}
	return ;
}

int maxDepth = 0;
vector<int > temp, ans; 
//深度优先搜索找深度最高的叶子结点，反过来也可以当作根节点； 
void DFS(int nowNode, int depth, int pre) {
	if(depth > maxDepth) {//找到最大深度; 
		temp.clear();
		temp.push_back(nowNode);
		maxDepth = depth; 
	}else if(maxDepth == depth) {//最大深度的根节点不可能是中间结点; 
		temp.push_back(nowNode); 
	}
	 for(int i = 0 ; i < node[nowNode].size(); i++) {//不要把i当作nowNode的孩子，其孩子应该是node[nowNode][i]; 
	 	if(node[nowNode][i] == pre) continue;//因为是无权图，互指，所以防止循环走回头路;
		 DFS(node[nowNode][i], depth + 1, nowNode);//遍历孩子找出最高深度; 
	 }
} 

int main () {
	scanf("%d", &n);
	for(int i = 0; i < n-1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		node[a].push_back(b);
		node[b].push_back(a);
	}
	init();//初始化; 
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < node[i].size(); j++) {
			int u = i, v = node[i][j];
			Union(u, v);//一条边上的两个结点连到一个集合里面; 
		}
	}//找出了所有的连通块;
	int block = 0;
	for(int i = 1; i <= n; i++) {
		if(vis[findRoot(i)] == false ){
			block++;//找出集合（连通块的个数）； 
			vis[findRoot(i)] = true;//i所在的集合标记; 
		}
	}
	if(block != 1) {
		printf("Error: %d components",block);//不止一块连通块; 
	}else {//只有一块连通块且节点数 = 边数+1,则说明是树; 
			//-1是前驱结点，因为是无权图，防止走回头路； 
			DFS(1, 1, -1);//找出最大深度和最大深度时的根集合ans；
			ans = temp;//vector可以直接赋值;
			DFS(ans[0], 1, -1);//以ans的某个结点为根节点再遍历一次得到集合b，这样找两遍才能得到答案，不然只有部分答案;
			for(int i = 0; i < temp.size(); i++) {
				ans.push_back(temp[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;
} 

三个命题：
①从任意顶点x出发遍历树，得到的最深结点一定是所求根节点的一部分(一侧)。

也就是说从任何一个结点出发，最深的那个叶子结点一定是可以使得这棵树最大深度的根节点。

证明：

假设树有直径RL（树的最大深度叫做直径），从R出发经过O到达L，RL长度最长。

前提条件（且一定满足的，因为树一定有最深深度）：树的最大直径为RL。

假设：从某一个结点X出发，同样经过O遍历到了最深深度叶子结点Y，Y既不是R也不是O

证明：因为同经过一个结点O，根据前提条件RL最大，应有RO和OL最大，所以XO是比RO小的，所有就有OY>OL,所有就又RL<RY，Y才是以R为根节点的最大树高度的叶子节点，即比原来的最大树高还高，不满足题意。

结论：所以就由从任何结点x进行树的遍历，得到的最深结点一定是R或者L，其中的一个，这样才能保证树的最大高度是定值，即所求根节点集合的一部分。

②树中的所有直径肯定是相交于一个点或者一个公共重合区间（线段）。

假设：树中的两条直径不相交

证明：树是连通图，两条直径肯定中间肯定有线段与之相连，使其连通，因此有树中的直径肯定相交于同一点或者公共重合区间。

③两次遍历的结果的并集为所求的根节点的结合。

一次遍历只能得到直径交点的一侧的答案，还要再根据答案反着遍历一次树才能得到答案。