Cod sursa(job #1294297)

Utilizator nicnic28nichita trita nicnic28 Data 17 decembrie 2014 11:09:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");

#define pb push_back

const int N=1+1e5;
int d[N],n;
vector<int> g[N];

int dfs(int s=1,int dpt=1){      //vreau sa returnez nodul cu cel mai lung drum catre el
    int dmax=s;
    for(int i=0 ; i<g[s].size() ; i++){
        if(!d[g[s][i]]){
            d[g[s][i]]=dpt+1;
            int x=dfs(g[s][i],dpt+1);
            if(d[x]>d[dmax]) dmax=x;
        }
    }
    return dmax;
}

int main()
{
    int x,y;
    in>>n;
    while(in>>x>>y){
        g[x].pb(y);
        g[y].pb(x);
    }
    d[1]=1;
    int xmax=dfs();
    for(int i=1 ; i<=n ; i++){
        d[i]=0;
    }
    d[xmax]=1;
    int diam=d[dfs(xmax)];
    out<<diam;
    return 0;
}