Cod sursa(job #2398488)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 5 aprilie 2019 16:27:47
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

const int N = 1e5 + 5;


vector<int> graph[N];
int n, answer, last;
int dist[N];

void Read()
{
    f >> n;

    for(int i = 1; i < n; ++i)
    {
        int a, b;
        f >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void bfs(int node)
{
    queue<int> q;

    q.push(node);
    dist[node] = 1;

    while(!q.empty())
    {
        int temp = q.front();
        q.pop();
        for(auto v : graph[temp])
            if(!dist[v])
            {
                dist[v] = dist[temp] + 1;
                q.push(v);
                last = v;
            }
    }
}

void Solve()
{
    bfs(1);
    memset(dist, 0, sizeof(dist));
    bfs(last);

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

    g << maxim << "\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}