Cod sursa(job #1630555)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 5 martie 2016 10:03:23
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<vector<int> > G;
vector<int> D1, D2;
vector<bool> viz1, viz2;
int N, capatDiam2, capatDiam1, iCapatDiam1, iCapatDiam2;

void dfs(int nod, int d)
{
    if(viz1[nod])
        return;
    D1[nod] = d;
    viz1[nod] = 1;
    if(d > capatDiam1){
        capatDiam1 = d;
        iCapatDiam1 = nod;
    }
    for(int i=0; i<G[nod].size(); ++i)
        dfs(G[nod][i], d+1);
}

void dfs2(int nod, int d)
{
    if(viz2[nod])
        return;
    viz2[nod] = 1;
    D2[nod] = d;
    if(d > capatDiam2){
        capatDiam2 = d;
        iCapatDiam2 = nod;
    }
    for(int i=0; i<G[nod].size(); ++i)
        dfs2(G[nod][i], d+1);
}

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

    scanf("%d", &N);
    D1.assign(N+2, 0);
    D2.assign(N+2, 0);
    viz1.assign(N+2, 0);
    viz2.assign(N+2, 0);
    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);
    dfs2(iCapatDiam1, 1);
    cout<<capatDiam2<<'\n';
    //cout<<iCapatDiam1<<' '<<iCapatDiam2;

    return 0;
}