1021. Deepest Root (25)
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<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 10000
int map[MAX][MAX];
int N;
int deep=1,maxdeep=0;
int collection[MAX];
int visited[MAX];
class node{
public:
int n;
int deep;
bool operator < (const node &n)const{
return deep > n.deep;
}
};
void dfs(int start){
collection[start]=1;
for(int i=1;i<=N;++i){
if(map[start][i]==1&&!collection[i]){
deep++;
if(deep>maxdeep) {
maxdeep=deep;
}
dfs(i);
deep--;
}
}
}
void dfs1(int start){
visited[start]=1;
for(int i=1;i<=N;++i){
if(map[start][i]==1&&!visited[i]){
dfs1(i);
}
}
}
int main(){
cin>>N;
int a,b;
for(int i=0;i<N-1;++i){
cin>>a>>b;
map[a][b]=1;
map[b][a]=1;
}
int cnt=0;
memset(visited,0,N+1);
for(int i=1;i<=N;++i){
if(visited[i]!=1){
dfs1(i);
cnt++;
}
}
if(cnt>=2){
cout<<"Error: "<<cnt<<" components";
return 0;
}
vector<node> vec;
for(int i=1;i<=N;++i){
memset(collection,0,sizeof(collection));
dfs(i);
node n;
n.n=i;
n.deep=maxdeep;
vec.push_back(n);
deep=1;
maxdeep=0;
}
sort(vec.begin(),vec.end());
cout<<vec[0].n<<endl;
for(int i=1;i<vec.size()-1;++i){
if(vec[i-1].deep>vec[i].deep)
break;
else{
cout<<vec[i].n<<endl;
}
}
return 0;
}
近期评论