problem
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
tip
answer
#include <cassert>
#include <set>
#include <iostream>
#include <vector>
#include <cstring>
#define Max 10010
#define fi first
#define se second
using namespace std;
int N;
int Root[Max], V[Max];
vector<int > E[Max];
set<int > S, Last;
set<int>::iterator it;
void Init(){
for(int i = 1; i <= N; i++){
Root[i] = i;
}
}
int Find(int i){
if(Root[i] != i) Root[i] = Find(Root[i]);
return Root[i];
}
void Union(int a, int b){
int ra = Find(a);
int rb = Find(b);
if(ra == rb) return ;
Root[ra] = Find(Root[rb]);
}
int TreeNum() {
int num = 0;
for(int i = 1; i <= N; i++){
if(Root[i] == i) num++;
}
return num;
}
int DFS(int t, int deep, int &maxD){
if(deep > maxD){
maxD = deep;
S.clear();
S.insert(t);
}
if(deep == maxD){
S.insert(t);
}
V[t] = 1;
for(int i = 0; i < E[t].size(); i ++){
if(!V[E[t][i]]){
DFS(E[t][i], deep+1, maxD);
}
}
}
void InitV(){
memset(V, 0, sizeof(V));
}
void PrintStatus(){
for(it = S.begin(); it != S.end(); it++){
cout<<*it<<" ";
}
cout<<endl;
}
int main(){
// freopen("test.txt", "r", stdin) ;
ios::sync_with_stdio(false);
//N<= 10000
cin>>N;
if(N == 0){
assert(false);
cout<<"0"<<endl;
}
Init();
int a, b;
for(int i = 0; i < N-1; i++) {
cin>>a>>b;
E[a].push_back(b);
E[b].push_back(a);
Union(a, b);
}
if(TreeNum() > 1) {
cout<<"Error: "<<TreeNum()<<" components";
}else{
int maxD = 0, deepN;
DFS(1, 0, maxD);
// PrintStatus();
for(it = S.begin(); it != S.end(); it++){
Last.insert(*it);
deepN = *it;
}
maxD = 0;
// cout<<deepN<<endl;
InitV();
DFS(deepN, 0, maxD);
// PrintStatus();
for(it = S.begin(); it != S.end(); it++){
Last.insert(*it);
}
for(it = Last.begin(); it != Last.end(); it++){
cout<<*it<<endl;
}
}
return 0;
}
exprience