Cod sursa(job #2094923)

Utilizator PaulTPaul Tirlisan PaulT Data 26 decembrie 2017 18:50:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;

VVI G;
VB v;
int n, dmax, node, root = 1;

void ReadGraph();
void Df(int x, int d);
void Write();

int main()
{
    ReadGraph();
    Write();
}

void Df(int x, int d)
{
    v[x] = true;
    if (d > dmax)
    {
        dmax = d;
        node = x;
    }
    for (const int& y : G[x])
        if (!v[y])
            Df(y, d + 1);
}

void Write()
{
    ofstream fout("darb.out");
    Df(root, 0);
    root = node;
    dmax = 0;
    v = VB(n + 1);
    Df(root, 0);
    fout << dmax + 1;
    fout.close();
}

void ReadGraph()
{
    ifstream fin("darb.in");
    fin >> n;
    G = VVI(n + 1);
    v = VB(n + 1);
    int x, y;
    for (int i = 1; i < n; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fin.close();
}