Cod sursa(job #1713624)

Utilizator Emy1337Micu Emerson Emy1337 Data 6 iunie 2016 01:17:18
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN=100000;

int n, x, y, start, maxy;
int dim[MAXN], viz[MAXN];
vector < int > graf[MAXN];
queue < int > coada;

void bfs()
{
    while(!coada.empty())
    {
        int nod = coada.front();
        coada.pop();
        viz[nod] = 1;

        for(auto it: graf[nod])
            if(!viz[it])
            {
                viz[it] = 1;
                dim[it] = dim[nod] +1;
                coada.push(it);
            }
    }
}

int main()
{
    fin >> n;

    while(fin>> x >> y)
    {
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    coada.push(1);
    bfs();
    for(int i=1; i<=n; i++)
        maxy=max(maxy,dim[i]);


    for(int i=1; i<=n; i++)
        if(dim[i] == maxy)
        {
            start = i;
            break;
        }

    fill(viz+1, viz+n+1, 0);
    fill(dim+1, dim+n+1, 0);
    coada.push(start);
    bfs();

    for(int i=1; i<=n; i++)
        maxy=max(maxy,dim[i]);

    for(int i=1; i<=n; i++)
    {
        if(dim[i] == maxy)
        {
            fout<<dim[i]+1;
            break;
        }
    }



}