Welcome, guest! Login / Register - Why register?
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

Your Name: Code Language: