Cod sursa(job #1632405)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 6 martie 2016 09:35:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int> > G;
int N, capat2, capat1, iCapat1, iCapat2;

void dfs(int nod, int d, int prec)
{
    if(d > capat1){
        capat1 = d;
        iCapat1 = nod;
    }
    for(int i=0; i<G[nod].size(); ++i)
        if(G[nod][i] != prec)
            dfs(G[nod][i], d+1, nod);
}

void dfs2(int nod, int d, int prec)
{
    if(d > capat2){
        capat2 = d;
        iCapat2 = nod;
    }
    for(int i=0; i<G[nod].size(); ++i)
        if(G[nod][i] != prec)
            dfs2(G[nod][i], d+1, nod);
}

int main()
{
    freopen("darb.in", "rt", stdin);
    freopen("darb.out", "wt", stdout);

    scanf("%d", &N);
    G.assign(N+1, vector<int>());
    int x, y;
    for(int i=1; i<N; ++i){
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 1, -1);
    dfs2(iCapat1, 1, -1);
    cout<<capat2<<'\n';
    return 0;
}