Cod sursa(job #1094290)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 29 ianuarie 2014 10:46:11
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Tree {
  public:
    static const int NIL = -1;

    Tree(const int _v = 0):
      v(_v),
      edges(vector< vector<int> >(_v, vector<int>())) {}

    int V() const {
        return v;
    }

    vector<int>::const_iterator EdgesBegin(const int x) const {
        return edges[x].cbegin();
    }

    vector<int>::const_iterator EdgesEnd(const int x) const {
        return edges[x].cend();
    }

    void AddEdge(const int x, const int y) {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    int GetDiameter() const {
        int x = 0, diameter = 0;
        vector<int> distances;
        BFS(x, distances);
        for (int y = 0; y < v; ++y)
            if (distances[y] > distances[x])
                x = y;
        BFS(x, distances);
        for (int y = 0; y < v; ++y)
            diameter = max(diameter, distances[y]);
        return diameter;
    }

  private:
    int v;
    vector< vector<int> > edges;

    void BFS(const int source, vector<int> &distances) const {
        distances = vector<int>(v, -1);
        queue<int> q;
        distances[source] = 0;
        q.push(source);
        for (; !q.empty(); q.pop()) {
            int x = q.front();
            for (const auto &y: edges[x]) {
                if (distances[y] == -1) {
                    distances[y] = distances[x] + 1;
                    q.push(y);
                }
            }
        }
    }
};

Tree T;
int Diameter;

void Solve() {
    Diameter = T.GetDiameter();
}

void Read() {
    ifstream in("darb.in");
    int v;
    in >> v;
    T = Tree(v);
    for (int i = 0; i < v - 1; ++i) {
        int x, y;
        in >> x >> y;
        --x;
        --y;
        T.AddEdge(x, y);
    }
    in.close();
}

void Print() {
    ofstream out("darb.out");
    out << Diameter << "\n";
    out.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}