Cod sursa(job #1570407)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 16 ianuarie 2016 15:08:40
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define pb push_back
#define NMax 100005

using namespace std;
vector<int> G[NMax];
queue<int>Q;
int N, x, y, d[NMax], viz[NMax], ultim, i, rez;
void bfs(int x)
{
    int i, l, nod;
    d[x]=1;
    viz[x]=1;
    Q.push(x);
    while(!Q.empty())
    {
        nod=Q.front();
        l=G[nod].size();
        for(i=0;i<l;i++)
            if(!viz[G[nod][i]])
                {
                    Q.push(G[nod][i]);
                    d[G[nod][i]]=d[nod]+1;
                    viz[G[nod][i]]=1;
                    rez=d[G[nod][i]];
                    ultim=G[nod][i];
                }
        Q.pop();
    }
}
int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);

    scanf("%d",&N);
    for(i=1;i<N;i++)
    {
        scanf("%d %d",&x,&y);
        G[x].pb(y);
        G[y].pb(x);
    }
    bfs(1);
    memset(d,0,sizeof(d));
    memset(viz,0,sizeof(viz));
    bfs(ultim);
    printf("%d\n",rez);
    return 0;
}