Cod sursa(job #1939154)

Utilizator nedelcu11Nedelcu Mihai Vlad nedelcu11 Data 25 martie 2017 15:03:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream f("darb.in");ofstream g("darb.out");
int n,Sol,viz[Nmax],D[Nmax];
vector <int> G[Nmax];
queue <int> Q;
int main()
{   f>>n;
    for(int x,y,i=1;i<=n-1;++i)
        {f>>x>>y; G[x].push_back(y); G[y].push_back(x); }
    int Nod;
    Q.push(1); viz[1]=1;
    while(!Q.empty())
    {   Nod=Q.front(); Q.pop();
        vector <int> :: iterator it=G[Nod].begin(), sf=G[Nod].end();
        for(;it!=sf;++it)
            {if(viz[(*it)]==0) {viz[(*it)]=1; Q.push((*it));}}
    }
    Q.push(Nod); viz[Nod]=2; D[Nod]=1;
    while(!Q.empty())
    {   Nod=Q.front(); Q.pop();
        vector <int> :: iterator it=G[Nod].begin(), sf=G[Nod].end();
        for(;it!=sf;++it)
            if(viz[(*it)]!=2)
            {   D[(*it)]=D[Nod]+1; viz[(*it)]=2; Q.push((*it));
                Sol=max(Sol,D[(*it)]);
            }
    }
    g<<Sol<<" "; g.close(); return 0;
}