Cod sursa(job #1762611)

Utilizator CaterpillerLeaf Caterpiller Caterpiller Data 23 septembrie 2016 21:39:25
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <queue>

class SimpleTree
{
    int mSize;
    std::vector<int> *edges; //rooted at 1
public:
    SimpleTree(int size)
    {
        mSize = size + 1;
        edges = new std::vector<int>[mSize];
    }
    std::vector<int> computeDistancesFromSource(int source)
    {
        std::vector<int> distances(mSize, -1);
        if (source <= 0 || source >= mSize) return distances;
        std::queue<int> bfs_queue;

        distances[source] = 0;
        bfs_queue.push(source);
        while (!bfs_queue.empty()) {
            int current_vertex = bfs_queue.front();
            bfs_queue.pop();

            for (int vertex : edges[current_vertex]) {
                if (distances[vertex] == -1) {
                    distances[vertex] = distances[current_vertex] + 1;
                    bfs_queue.push(vertex);
                }
            }
        }
        return distances;
    }
    void addEdge(int a, int b)
    {
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    int getDiameter()
    {
        auto distances = computeDistancesFromSource(1);

        int furthest_vertex = 1;
        for (int i = 2; i < mSize; ++i) {
            if (distances[i] > distances[furthest_vertex]) furthest_vertex = i;
        }
        distances = computeDistancesFromSource(furthest_vertex);

        int diameter = 0;
        for (int distance : distances) {
            if (distance > diameter) diameter = distance;
        }

        return diameter + 1;
    }
};

int main()
{
    std::ifstream input("darb.in");
    std::ofstream output("darb.out");
    int n;

    input >> n;
    SimpleTree tree(n);
    for(int i = 1; i < n; ++i) {
        int a, b;
        input >> a >> b;
        tree.addEdge(a, b);
    }
    output << tree.getDiameter() << '\n';
}