Cod sursa(job #1413009)

Utilizator matei_cChristescu Matei matei_c Data 1 aprilie 2015 18:02:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

#define maxn 100005

int N ;

vector<int> graf[maxn] ;

queue<int> coada ;

int dist[maxn], diametru, ultimu ;

void bfs(int start)
{
    memset( dist, 0, sizeof(dist) ) ;

    coada.push(start) ;
    dist[start] = 1 ;

    while( coada.empty() == false )
    {
        int nod = coada.front() ;
        coada.pop() ;

        for(size_t i = 0; i < graf[nod].size(); ++i)
        {
            int vecin = graf[nod][i] ;

            if( dist[vecin] == 0 )
            {
                coada.push(vecin) ;
                dist[vecin] = dist[nod] + 1 ;

                diametru = dist[vecin] ;
                ultimu = vecin ;
            }
        }
    }
}

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);

        graf[x].push_back(y) ;
        graf[y].push_back(x) ;
    }

    bfs(1) ;

    bfs(ultimu) ;

    printf("%d", diametru);

	return 0 ;
}