Cod sursa(job #1585198)

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

using namespace std;

const int Mn = 1e5 + 6;

int n,vert,sol,pos;
char buff[Mn];
vector< int > g[Mn];

void read(int &num)
{
    num = 0;
    char sign = '+';

    while (!isdigit(buff[pos]))
    {
        sign = buff[pos];

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    while (isdigit(buff[pos]))
    {
        num = num * 10 + buff[pos] - '0';

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    if (sign == '-')
       num *= -1;
}

void dfs(int node,int parent,int depth)
{
    if (depth > vert)
       vert = depth,sol = node;

    for (int i = 0;i < g[node].size();i++)
        if (g[node][i] != parent)
           dfs(g[node][i],node,depth + 1);
}

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

     read(n);

     for (int i = 1;i <= n;i++)
     {
         int x,y;
         read(x);
         read(y);
         g[x].push_back(y);
         g[y].push_back(x);
     }

     dfs(1,0,1);
     dfs(vert,0,1);

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

  return 0;
}