Cod sursa(job #2524170)

Utilizator trifangrobertRobert Trifan trifangrobert Data 15 ianuarie 2020 10:17:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100005;
const int INF = (1 << 30);
int N, dist[NMAX];
vector <int> graph[NMAX];

void bfs(int start)
{
    for (int i = 1;i <= N;++i)
        dist[i] = INF;
    dist[start] = 1;
    queue <int> q;
    q.push(start);
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (auto &x : graph[node])
            if (dist[x] > dist[node] + 1)
            {
                dist[x] = dist[node] + 1;
                q.push(x);
            }
    }
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> N;
    for (int i = 1;i < N;++i)
    {
        int u, v;
        fin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    bfs(1);
    int mx = 0, node;
    for (int i = 1;i <= N;++i)
        if (dist[i] > mx)
        {
            mx = dist[i];
            node = i;
        }
    bfs(node);
    int best = 0;
    for (int i = 1;i <= N;++i)
        best = max(best, dist[i]);
    fout << best << "\n";
    fin.close();
    fout.close();
    return 0;
}