Cod sursa(job #2224996)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 25 iulie 2018 17:32:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef vector<vector<int>> Graph;

const string IN_FILE = "darb.in";
const string OUT_FILE = "darb.out";

vector<int> bfs(const Graph& graph, const int source) {
    queue<int> q;
    auto distances = vector<int>(int(graph.size()), -1);
    distances[source] = 0;
    for (q.push(source); !q.empty(); q.pop()) {
        const int u = q.front();
        for (const auto& v : graph[u]) {
            if (distances[v] == -1) {
                distances[v] = distances[u] + 1;
                q.push(v);
            }
        }
    }
    return distances;
}

int findMaxIndex(const vector<int>& values) {
    int index = -1;
    for (int i = 0; i < int(values.size()); i++) {
        index = index == -1 || values[i] > values[index] ? i : index;
    }
    return index;
}

int getDiameter(const Graph& tree) {
    const int from = findMaxIndex(bfs(tree, 0));
    const auto distances = bfs(tree, from);
    const int to = findMaxIndex(distances);
    return distances[to];
}

inline void addEdge(Graph& graph, const int u, const int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

Graph readTree() {
    ifstream in(IN_FILE);
    int n;
    in >> n;
    auto tree = Graph(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        in >> u >> v;
        addEdge(tree, u - 1, v - 1);
    }
    in.close();
    return tree;
}

void writeDiameter(const int diameter) {
    ofstream out(OUT_FILE);
    out << diameter + 1 << "\n";
    out.close();
}

int main() {
    const auto& tree = readTree();
    const int diameter = getDiameter(tree);
    writeDiameter(diameter);
    return 0;
}