Cod sursa(job #1962508)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 11 aprilie 2017 20:32:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

vector<int> arb[MAXN];
int n;
bool viz[MAXN];
int maxim = -1, who;

const int SIZE = 1000000;
struct InParsare
{

    char buffer[SIZE];
    int index;
    inline char next_char()
    {
        if(index == SIZE)
        {
            fread(buffer,1,SIZE,stdin);
            index = 0;
            return next_char();
        }
        return buffer[index++];
    }
    InParsare()
    {
        freopen("darb.in", "r", stdin);
        index = 0;
        fread(buffer,1,SIZE,stdin);
    }
    inline InParsare& operator >> (int &x)
    {
        x = 0;
        char c;
        for(c = next_char(); c < '0' || c > '9'; c = next_char());
        for(;c >= '0' && c <= '9'; c = next_char())
            x = x * 10 + c - '0';
        return *this;
    }
}in;

void citire()
{
    in>>n;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        in>>a>>b;
        arb[a].push_back(b);
        arb[b].push_back(a);
    }
}

void dfs1(int nod,int level)
{
    viz[nod] = 1;
    if(level > maxim)
    {
        maxim = level;
        who = nod;
    }
    for(auto it = arb[nod].begin();it != arb[nod].end(); ++it)
    {
        if(!viz[*it])
        {

            dfs1(*it, level + 1);
        }
    }
}

void dfs2(int nod,int level)
{
    viz[nod] = 1;
    if(level > maxim)
    {
        maxim = level;
        who = nod;
    }
    for(auto it = arb[nod].begin();it != arb[nod].end(); ++it)
    {
        if(!viz[*it])
        {
            dfs2(*it, level + 1);
        }
    }
}

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

    citire();

    dfs1(1,0);
    maxim = -1;
    memset(viz,0,sizeof(viz));
    dfs2(who,0);
    printf("%d\n",maxim + 1);

    return 0;
}