Cod sursa(job #2204281)

Utilizator IsacLucianIsac Lucian IsacLucian Data 15 mai 2018 11:48:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define oo 100000000

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

int n;
vector<int>L[100005];
int dist[100005],grad[100005];
queue<int>q;

void Init()
{
    for(int i=1;i<=n;i++)
        dist[i]=oo;
}

void Bfs(int nod)
{
    dist[nod]=0;
    q.push(nod);

    while(!q.empty())
    {
        int x=q.front();
        q.pop();

        for(auto i:L[x])
            if(dist[i]>dist[x]+1)
            {
                dist[i]=dist[x]+1;
                q.push(i);
            }
    }
}

int main()
{
    int i,x,y,start,maxim,poz;
    fin>>n;

    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        grad[y]++;
        L[x].push_back(y);
        L[y].push_back(x);
    }


    for(i=1;i<=n;i++)
        if(!grad[i])
        {
            start=i;
            break;
        }

    Init();
    Bfs(start);
    poz=maxim=0;
    for(i=1;i<=n;i++)
        if(maxim<dist[i])
        {
            maxim=dist[i];
            poz=i;
        }

    Init();
    Bfs(poz);
    maxim=0;

    for(i=1;i<=n;i++)
        maxim=max(maxim,dist[i]);

    fout<<maxim+1<<"\n";
    return 0;
}