PAT A1021

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "stdio.h"
#include "math.h"
#include "string.h"
#include "iostream"
//#include "stdlib.h"
#include "vector"
#include "set"
#include "map"
//#include "stack"
#include "queue"
#include "algorithm"
using namespace std;

//typedef long long LL;
const int N = 10010;
vector<int> G[N];//邻接表
vector<int> deepestRoot, ans;
bool vis[N] = {false};//标记顶点i是否已经被访问
int n, maxDepth = -1;

//dfs遍历v所在的连通块
void dfs(int v,int depth){
if (depth > maxDepth) {
maxDepth = depth;
deepestRoot.clear();
deepestRoot.push_back(v);

}else if(depth == maxDepth){
deepestRoot.push_back(v);
}
vis[v] = true;//v点被访问
for (int i = 0; i < G[v].size(); i++) {
if (vis[G[v][i]] == false) {//如果顶点G[v][i]未被访问
dfs(G[v][i], depth + 1);
}
}
}
int block = 0;
void dfstrave(){
for (int i = 1; i <= n; i++) {
if (vis[i] == false) {
dfs(i, 0);
block++;
}
}
}

int main(){
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int a, b;
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
dfstrave();
memset(vis, false, sizeof(vis));
set<int> sRoot;
if (block == 1) {//是树
for (int i = 0 ; i < deepestRoot.size(); i++) {
sRoot.insert(deepestRoot[i]);
}
dfs(deepestRoot[0], 0);
for (int i = 0 ; i < deepestRoot.size(); i++) {
sRoot.insert(deepestRoot[i]);
}
set<int>::iterator it = sRoot.begin();
for (; it != sRoot.end() ; it++) {
printf("%d\n", *it);
}
}else{
printf("Error: %d components\n", block);
}

return 0;
}

并查集版本(算法笔记):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
    #include "stdio.h"
#include "math.h"
#include "string.h"
#include "iostream"
//#include "stdlib.h"
#include "vector"
#include "set"
#include "map"
//#include "stack"
#include "queue"
#include "algorithm"
using namespace std;

const int N = 110;
vector<int> G[N];//邻接表

bool isRoot[N];//记录每个结点是否作为某个集合的根结点
int father[N];//并查集
int findFather(int x){
int a = x;
while (x != father[x]) {
x = father[x];
}
//路径压缩
while (a != father[a]) {
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
void Union(int a, int b) {//合并a和b所在的集合
int faA = findFather(a);
int faB = findFather(b);
if (faA != faB) {
father[faA] = faB;
}
}
void init(int n){//并查集初始化
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
int calBlock(int n){//计算连通块个数
int Block = 0;
for (int i = 1; i <= n; i++) {
isRoot[findFather(i)] = true;//i的根节点是findFather(i)
}
for (int i = 1; i <= n; i++) {
Block += isRoot[i];//累加根结点个数
}
return Block;
}
int maxH = 0;//最大高度
vector<int> temp, ans;//temp临时存放dfs的最远结点结果,ans保存答案

//dfs函数,u为当前访问结点编号,height为当前树高,pre为u的父节点
void dfs(int u, int height, int pre){
if (height > maxH) {//获得了更大的树高
temp.clear();//清空temp
temp.push_back(u);//将当前结点u加入temp中
maxH = height;//更新最大树高
}else if(height == maxH){
temp.push_back(u);//加入当前结点到temp中
}
for (int i = 0; i < G[u].size(); i++) {//遍历u的所有子节点
//由于邻接表中存放无向图,因此需要跳过回去的边
if (G[u][i] == pre) continue;
dfs(G[u][i], height + 1, u);//访问子节点
}

}

int main(){
int a, b, n;
scanf("%d", &n);
init(n);
for (int i = 1; i < n; i++) {
scanf("%d%d", &a, &b);
G[a].push_back(b);//边a->b
G[b].push_back(a);//边b->a
Union(a, b);//合并a和b所在的集合
}
int Block = calBlock(n);//计算集合数目
if (Block != 1) {//不止一个连通块
printf("Error: %d components\n", Block);
} else {
dfs(1, 1, -1);//从1号结点开始dfs,初始高度为1
ans = temp;//temp为集合A,赋值给ans
dfs(ans[0], 1, -1);//从任意一个根节点开始遍历
for (int i = 0; i < temp.size(); i++) {
ans.push_back(temp[i]);//此时temp为集合b,将其加到ans中
}
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]);
}
}
// dfs(1, 1, -1);//从1号结点开始dfs,初始高度为1
// set<int> setofRoot;
// for (int i = 0; i < temp.size(); i++) {
// setofRoot.insert(temp[i]);
// }
// dfs(temp[0], 1, -1);
// for (int i = 0; i < temp.size(); i++) {
// setofRoot.insert(temp[i]);
// }
// for (set<int>::iterator it = setofRoot.begin(); it != setofRoot.end(); it++) {
// printf("%d\n", *it);
// }

}
return 0;
}

注释中是用集合实现deepest root的储存