Cod sursa(job #1411111)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 31 martie 2015 14:11:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using Graph = std::vector<std::vector<int>>;


std::pair<int, int> bfs(const Graph &adj, int src)
{
    std::vector<bool> visited(adj.size(), false);
    std::queue<std::pair<int, int>> Q;

    Q.emplace(src, 1);
    visited[src] = true;

    std::pair<int, int> curr;
    while (!Q.empty()) {
        curr = Q.front();
        Q.pop();

        for (auto &neigh : adj[curr.first])
            if (!visited[neigh]) {
                visited[neigh] = true;
                Q.emplace(neigh, curr.second + 1);
            }
    }

    return curr;
}

int main()
{
    std::ifstream fin{"darb.in"};
    std::ofstream fout{"darb.out"};

    int N;
    fin >> N;

    Graph adj(N);
    for (auto i = 0; i < N; ++i) {
        int a, b;

        fin >> a >> b;
        adj[a - 1].push_back(b - 1);
        adj[b - 1].push_back(a - 1);
    }

    fout << bfs(adj, bfs(adj, 0).first).second;
    return 0;
}