Cod sursa(job #1994324)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 24 iunie 2017 17:57:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

int bfs(int node, std::vector<std::list<int>> &graph, std::vector<int> &dist) {

    std::vector<bool> check(graph.size(), false);
    std::list<int> myQ;

    myQ.push_back(node);
    check[node] = true;
    dist[node] = 1;

    int last;

    while (!myQ.empty()) {
        last = myQ.front();
        myQ.pop_front();
        for (int vertex : graph[last]) {
            if (!check[vertex]) {
                dist[vertex] = dist[last] + 1;
                check[vertex] = true;
                myQ.push_back(vertex);
            }
        }
    }

    return last;
}

int main() {
    std::ifstream fileIn("darb.in");
    std::ofstream fileOut("darb.out");

    int nV;
    fileIn >> nV;

    std::vector<std::list<int>> graph(nV + 1);

    int a, b;

    for (int i(1); i < nV; i++) {
        fileIn >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    std::vector<int> dist(nV + 1, -1);
    int node = bfs(1, graph, dist);

    node = bfs(node, graph, dist);

    fileOut << dist[node];

    fileIn.close();
    fileOut.close();
    return 0;
}