Cod sursa(job #2161408)

Utilizator dragosmdvMoldovan Dragos dragosmdv Data 11 martie 2018 18:24:38
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector <int> v[100001];
queue <int > q;
int n, dia, cont, a, et, num, b, freq[100001], parent[100001];

void bfs( int x)
{
    q.push(x);
    freq[x]=1;
    parent[x]=1;
    while(!q.empty())
    {
        int aux=q.front();
        q.pop();
        for(int i=0; i<v[aux].size(); i++)
        {
            cont++;
            x=v[aux][i];
            if(freq[x]==0)
            {
                parent[x]=parent[aux]+1;
                freq[x]=1;
                q.push(x);
                num=x;
                dia=parent[x];
            }
        }
    }
}

int main()
{
    fin>>n;
    for(int i=1; i<=n-1; i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    cont=0;
    bfs(1);


    for(int i=1; i<=n; i++)
    {
        freq[i]=0;
        parent[i]=0;
    }
    bfs(num);
    fout<<dia;
    return 0;
}