pat 1021 deepest root

一点教训

首先声明,大家都用并查集做这道题,我没想到,故而用了最笨的办法,dfs

Attention:
求无向图的连通分量数目的方法有俩种:

  1. DFS(最笨)
    1. 并查集

上代码:

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10010
using namespace std;
struct node
{
vector<int> child;
}Node[MAX];
int N;
int max_h = 0;
int max(int a , int b)
{
return a>b? a:b;
}
bool visit[MAX] = {false};
void DFS(int root , int depth)
{
visit[root] = true;
max_h = max(max_h , depth);
for(int i = 0 ; i< Node[root].child.size() ; ++i)
{
if(!visit[Node[root].child[i]])
DFS(Node[root].child[i] , depth+1);
}
}
int elem[MAX] = {0};
int cnt =0;
void DFS2(int root)
{
visit[root] = true;
for(int i = 0 ; i < Node[root].child.size() ; ++i)
{
if(!visit[Node[root].child[i]])
DFS2(Node[root].child[i]);
}
}
//connected componet numbers?
void calBlock()
{
for(int i = 1 ; i <= N ; ++i)
{
if(!visit[i])
{
++cnt;
DFS2(i);
}
}
}
int main()
{
cin>>N;
if(N == 1)
{
cout<<1<<endl;
return 0;
}
int i;
for(i = 0 ; i < N-1; ++i)
{
int fa , son;
cin>>fa>>son;
Node[fa].child.push_back(son);
Node[son].child.push_back(fa);
}
int j;
bool isError = false;//标示是否都可以连通
for(i = 1; i<= N ; ++i)
{
DFS(i , 0);
for(j = 1; j <= N ; ++j)
{
if(!visit[j])
{
isError = true;
}
}
if(isError)
break;
fill(visit , visit+MAX , false);
elem[i] = max_h;
max_h = 0;
}
/* for(i = 1; i <=N ; ++i)
{
cout<<elem[i]<<" ";
}
*/
if(!isError)
{
//sort(elem+1 , elem+N);
int max = elem[1];
for(i = 2; i <= N ; ++i)
{
if(max < elem[i])
{
max = elem[i];
}
}
for(i = 1 ; i <=N ; ++i)
{
if(max == elem[i])
cout<<i<<endl;
}
}
else
{
fill(visit , visit+MAX , false);
calBlock();
cout<<"Error: "<<cnt<<" components";
}
/* bool isF = true;
for(i = N ; i >=1; --i)
{
if(isF)
{
cout<<i<<endl;
isF = false;
}
else
{
if(elem[i] == elem[i+1])
cout<<i<<endl;
else
break;
}
}*/
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
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)
{
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;
}
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.push_back(u);
maxH = Height;
}
else if(Height == maxH)
{
temp.push_back(u);
}
for(int i = 0 ; i < G[u].size() ; ++i)
{
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);
G[b].push_back(a);
Union(a , b); //合并a和b所在的集合
}
int Block = calBlock(n); //计算集合数目(很巧妙的计算无向图的连通分量算法)
if(Block != 1)
printf("Error: %d components\n" , Block);
else
{
DFS(1 ,1 ,-1);
Ans = temp;
DFS(Ans[0] , 1 ,-1);
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;
}

热评文章