Cod sursa(job #2474702)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 15 octombrie 2019 18:54:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define N_MAX 100001
using namespace std;

vector<vector<int>> arb(N_MAX, vector<int>());

int n;

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

vector<int> dist(N_MAX);

int dfs(int x)
{
    queue<int> Q;
    Q.push(x);

    fill(dist.begin(),dist.end(), 0);

    int ret = x;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        for(auto& next : arb[node]){
            if(dist[next] == 0)
            {
                dist[next] = dist[node] + 1;
                Q.push(next);

                if(dist[next] > dist[ret]) ret = next;
            }
        }
    }

    return ret;

}
int main()
{
    fin >> n;

    for(int x, y, i = 1; i < n; ++i)
    {
        fin >> x >> y;

        arb[x].push_back(y);
        arb[y].push_back(x);
    }

    int next = dfs(1);
    fout << dist[dfs(next)] + 1;
}