Cod sursa(job #1108553)

Utilizator tudorv96Tudor Varan tudorv96 Data 15 februarie 2014 19:50:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <vector>
#include <fstream>
using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

const int N = 1e5 + 5;

vector <int> g[N];
int n, d[N], sol;

void dfs (int x, int tata) {
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (*it != tata) {
            d[*it] = d[x] + 1;
            dfs (*it, x);
        }
}

int main() {
    fin >> n;
    for (int x, y, i = 1; i < n; ++i) {
        fin >> x >> y;
        g[x].push_back (y);
        g[y].push_back (x);
    }
    d[1] = 1;
    dfs (1, -1);
    int nod = 1;
    for (int i = 2; i <= n; ++i)
        if (d[nod] < d[i])
            nod = i;
    d[nod] = 1;
    dfs (nod, -1);
    for (int i = 1; i <= n; ++i)
        sol = max(sol, d[i]);
    fout << sol;
}