Cod sursa(job #2103996)

Utilizator inquisitorAnders inquisitor Data 11 ianuarie 2018 00:09:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

int vertices, u, v, level[100001];

vector<int> adj[100001];

int BFS(int start)
{
    queue<int> q; q.push(start);

    for(int i = 1; i <= vertices; i++)
    {
        level[i] = 0;
    }

    level[start]++;

    while(1)
    {
        int current = q.front(); q.pop();

        for(int child : adj[current])
        {
            if(level[child] == 0)
            {
                q.push(child);

                level[child] = level[current] + 1;
            }
        }

        if(q.empty()) return current;
    }
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    scanf("%d", &vertices);

    for(int i = 1; i < vertices; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);

        adj[v].push_back(u);
    }

    printf("%d", level[BFS(BFS(1))]);

    return 0;
}