Cod sursa(job #1744107)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 19 august 2016 12:21:46
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,v[100001],maxs=-1,ns,a,b,i,coada[100001];
struct nod{
   int inf;
   nod *urm;
}*L[100001];
void adaugsf(nod *&vf,int val){
    nod *q;
    q=new nod;
    q->inf=val;
    q->urm=vf;
    vf=q;
}
void BFS(int k){
    nod *q;
    int p=1,u=1;
    coada[1]=k;
    while(p<=u){
        q=L[coada[p]];
        while(q!=0){
           if (v[q->inf]==0){
              v[q->inf]=v[coada[p]]+1;
              if (v[q->inf]>maxs){
                 maxs=v[q->inf];
                 ns=q->inf;
              }
              u++;
              coada[u]=q->inf;
           }
           q=q->urm;
        }
        p++;
    }
}
int main(){
    fin>>n;
    for (i=1;i<=n;i++)
        L[i]=0;
    for (i=1;i<=n;i++){
        fin>>a>>b;
        adaugsf(L[a],b);
        adaugsf(L[b],a);
    }
    BFS(1);
    maxs=-1;
    for (i=1;i<=n;i++)
        v[i]=0;
    BFS(ns);
    fout<<maxs+1;
    fin.close();
    fout.close();
    return 0;
}