Cod sursa(job #1699131)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 6 mai 2016 10:47:07
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
# include <fstream>
# include <vector>
# define DIM 100010
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> Lista[DIM];
int Marcat[DIM],c[DIM],n,i,x,y,p,u,nc,nv,maxim,poz;
int main () {
    fin>>n;
    for(i=1;i<n;i++){
        fin>>x>>y;
        Lista[x].push_back(y);
        Lista[y].push_back(x);
    }
    c[++u]=1;
    p=1;
    Marcat[1]=1;
    while(p<=u){
        nc=c[p];
        for(i=0;i<Lista[nc].size();i++){
            nv=Lista[nc][i];
            if(Marcat[nv]==0){
                Marcat[nv]=1+Marcat[nc];
                c[++u]=nv;
                if(Marcat[nv]>maxim){
                    maxim=Marcat[nv];
                    poz=nv;
                }
            }
        }
        p++;
    }
    for(i=1;i<=n;i++)
        Marcat[i]=0;
    u=0;
    c[++u]=poz;
    p=1;
    Marcat[poz]=1;
    while(p<=u){
        nc=c[p];
        for(i=0;i<Lista[nc].size();i++){
            nv=Lista[nc][i];
            if(Marcat[nv]==0){
                Marcat[nv]=1+Marcat[nc];
                c[++u]=nv;
                if(Marcat[nv]>maxim)
                    maxim=Marcat[nv];
            }
        }
        p++;
    }
    fout<<maxim<<"\n";
    return 0;
}