Cod sursa(job #1404662)

Utilizator c0rn1Goran Cornel c0rn1 Data 28 martie 2015 13:53:15
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 100008
#define inf 0x3f3f3f3f

using namespace std;

int n, last, diam;
vector<int> v[NMAX];
bitset<NMAX> viz;

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

void dfs(int x, int d)
{
   if (diam < d){
      last = x;
      diam = d;
   }
   viz[x] = 1;
   for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it){
      if (!viz[*it]){
         dfs(*it, d+1);
      }
   }
}

int main()
{
   freopen("darb.in", "r", stdin);
   freopen("darb.out", "w", stdout);
   read();
   dfs(1, 0);
   viz = 0;
   diam = 0;
   dfs(last, 0);
   printf("%d\n", diam+1);

   return 0;
}