Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as C++ by jafc ( 13 years ago )
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
vector < vector <int> > grafo(5005);
vector <int> camino;
int padre[5005], dist[5005];
bool worst[5005];
int r, t, N, sz, v, w, diam;
void leer(){
for(int i=0;i<N;i++){
scanf("%d",&sz;);
for(int j=0;j<sz;j++){
scanf("%d",&v);
grafo[i+1].push_back(v);
}
}
}
void bfs(int nodo){
queue <int> cola;
memset(dist,-1,sizeof dist);
cola.push(nodo);
dist[nodo]=0;
while(!cola.empty()){
t=cola.front();
cola.pop();
for(int i=0;i<grafo[t].size();i++){
r=grafo[t][i];
if(dist[r]==-1){
dist[r]=dist[t]+1;
padre[r]=t;
cola.push(r);
}
}
}
}
int main(){
while(scanf("%d",&N)){
grafo = vector < vector <int> > (N+1);
leer();
bfs(grafo[1][0]); int v = t;
bfs(v); int w = t;
int p=w;
while(p!=v){
camino.push_back(p);
p=padre[p];
}
camino.push_back(v);
diam=dist[w];
if(diam%2==0){
int rad=diam/2;
int c = camino[rad];
printf("Best Roots : %d\n",c);
}
else {
int rad=(diam+1)/2;
int c1=camino[rad];
int c2=camino[rad-1];
printf("Best Roots :");
if(c1<c2)printf(" %d %d\n",c1,c2);
else printf(" %d %d\n",c2,c1);
}
memset(worst,0,sizeof worst);
for(int i=1;i<=N;i++)
if(dist[i]==diam)worst[i]=1;
bfs(w);
for(int i=1;i<=N;i++)
if(dist[i]==diam)worst[i]=1;
printf("Worst Roots :");
for(int i=1;i<=N;i++)
if(worst[i])printf(" %d",i);
printf("\n");
grafo.clear();
camino.clear();
}
return 0;
}
Revise this Paste