Cod sursa(job #1861211)

Utilizator GinguIonutGinguIonut GinguIonut Data 28 ianuarie 2017 18:23:29
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>

#define nMax 100001
#define pb push_back
using namespace std;

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

int n, dist[nMax];
vector<int> G[nMax];

void dfs(int node, int tata)
{
    for(vector<int>::iterator it=G[node].begin(); it!=G[node].end();it++)
    {
        int fiu=*it;
        if(fiu==tata)
            continue;
        dist[fiu]=dist[node]+1;
        dfs(fiu, node);
    }
}

int main()
{
    int a, b, poz=0, Sol=0;
    fin>>n;
    for(int i=1; i<n; i++)
    {
        fin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1, 0);
    for(int i=1; i<=n; i++)
        if(dist[i]>=dist[poz])
            poz=i;
    dist[poz]=0;
    dfs(poz, 0);
    for(int i=1; i<=n; i++)
        Sol=max(Sol, dist[i]);
    fout<<Sol+1;
}