Cod sursa(job #1329937)

Utilizator MarianMMorosac George Marian MarianM Data 30 ianuarie 2015 00:59:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define DMAX 100002

int N;

struct Nod{
	int used, d;
	vector<int> Adj;
}A[DMAX];

void BFS(int root){
	int i, x, y;
	queue<int> Q;

	A[root].d = 0;
	Q.push(root);

	while (!Q.empty()){
		x = Q.front();
		A[x].used = 1;
		Q.pop();

		y = A[x].Adj.size();
		for (i = 0; i < y; i++){
			if (!A[A[x].Adj[i]].used){
				A[A[x].Adj[i]].d = A[x].d + 1;
				Q.push(A[x].Adj[i]);
			}
		}
	}
}

int main(){
	int i, j, x, y;

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

	scanf("%d", &N);

	for (i = 1; i < N; i++){
		scanf("%d %d", &x, &y);
		A[x].Adj.push_back(y);
		A[y].Adj.push_back(x);
	}

	// pt ca e graf orientat => root can be anywhere

	BFS(1);

	// get furthest point
	int MaxD = -1, Root = -1;
	for (i = 1; i <= N; i++){
		if (A[i].d > MaxD){
			MaxD = A[i].d;
			Root = i;
		}
		A[i].d = 0;
		A[i].used = 0;
	}

	BFS(Root);

	MaxD = -1;
	for (i = 1; i <= N; i++){
		if (A[i].d > MaxD){
			MaxD = A[i].d;
		}
	}

	printf("%d", MaxD + 1);

	return 0;
}