Cod sursa(job #2281620)

Utilizator maria15Maria Dinca maria15 Data 12 noiembrie 2018 16:20:04
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>

using namespace std;

int n, i, j, f[100002], g[100002], m, sol, maxim, c[100002], p, u, a, b, crt, nod;
vector<int> v[100002];

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

void dfs(int nod, int niv){
    g[nod] = niv;
    if(niv > m)
        m = niv;
    for(j=0;j<v[nod].size();j++){
        int vec = v[nod][j];
        if(g[vec] == 0)
            dfs(vec, niv+1);
    }
}

int main(){
    fin>>n;
    for(i=1;i<n;i++){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    p = u = 1;
    f[1] = 1;
    c[1] = 1;
    while(p<=u){
        crt = c[p];
        for(j=0;j<v[crt].size();j++){
            nod = v[crt][j];
            if(f[nod] == 0){
                f[nod] = f[crt] + 1;
                if(f[nod] > maxim){
                    maxim = f[nod];
                    sol = nod;
                }
                c[++u] = nod;
            }
        }
        p++;
    }
    dfs(sol, 1);
    fout<<m;
    return 0;
}