Cod sursa(job #2355546)

Utilizator LivcristiTerebes Liviu Livcristi Data 26 februarie 2019 09:49:10
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define NUM 100005
using namespace std;
vector<int> graf[NUM];
int n, lng, a, b;

int bfs(int nod)
{
    int dist[NUM] = {0};
    int aux;
    queue <int> coada;

    dist[nod] = 1;
    coada.push(nod);
    while(!coada.empty())
    {
        aux = coada.front();
        coada.pop();
        for(int i = 0; i < graf[aux].size(); ++i)
        {
            if(dist[graf[aux][i]] == 0)
            {
                coada.push(graf[aux][i]);
                dist[graf[aux][i]] = dist[aux] + 1;
            }
        }
    }

    int ind = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(dist[i] > lng)
        {
            lng = dist[i];
            ind = i;
        }
    }
    return ind;
}

int dist()
{
    int f1, f2;
    f1 = bfs(1);
    f2 = bfs(f1);
    return lng;
}
int main()
{
    ifstream f("darb.in");
    ofstream g("darb.out");
    f >> n;
    for(int i = 0; i < n; ++i)
    {
        f >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    g << dist();

    f.close();
    g.close();
}