Cod sursa(job #1585207)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 30 ianuarie 2016 20:56:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

const int Mn = 1e5 + 6;

int n,vert,sol,cnt;
bool used[Mn];
vector< int > g[Mn];

void dfs(int node)
{
    used[node] = 1;
    cnt++;

    if (cnt > sol)
       vert = node,sol = cnt;

    for (int i = 0;i < g[node].size();i++)
        if (!used[g[node][i]])
           dfs(g[node][i]);

    cnt--;
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);

     scanf("%d",&n);

     for (int i = 1;i <= n;i++)
     {
         int x,y;
         scanf("%d %d",&x,&y);
         g[x].push_back(y);
         g[y].push_back(x);
     }

     dfs(1);
     memset(used,0,sizeof(used));
     dfs(vert);

     printf("%d\n",sol);

  return 0;
}