Cod sursa(job #1260864)

Utilizator sunt_emoSunt emo sunt_emo Data 11 noiembrie 2014 18:22:58
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>

class Arb
{
    public:
    int id;
    std::vector<Arb *> vecs;
};

int solution(const Arb &node, std::vector<int> &dists)
{
    dists[node.id] = 0;
    if (node.vecs.size() == 0)
    {
        dists[node.id] = 1;
        return 1;
    }
    int b1 = 0, b2 = 0, ret = 0;
    for (int i = 0; i < (int) node.vecs.size(); i++)
    {
        if (dists[node.vecs[i]->id] == -1)
        {
            ret = std::max(solution(*node.vecs[i], dists), ret);
            if (dists[node.vecs[i]->id] > b1)
                b2 = b1, b1 = dists[node.vecs[i]->id];
            else if (dists[node.vecs[i]->id] > b2)
                b2 = dists[node.vecs[i]->id];
        }
    }
    dists[node.id] = b1 + 1;
    return std::max(b1 + b2 + 1, ret);
}

int main()
{
    std::ifstream in("darb.in");
    std::ofstream out("darb.out");
    int n, x, y;
    in >> n;
    std::vector<Arb> tree(n + 1);
    std::vector<int> dists(n + 1, -1);
    for (int i = 1; i <= n; i++)
        tree[i].id = i;
    for (int i = 0; i < n - 1; i++)
    {
        in >> x >> y;
        tree[x].vecs.push_back(&tree[y]);
        tree[y].vecs.push_back(&tree[x]);
    }
    out << solution(tree[1], dists) << '\n';
    in.close(), out.close();
}