Cod sursa(job #1222785)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 24 august 2014 13:21:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100010

vector<int> Gr[MAX];
queue<int> Q;
int N, D[MAX];

int Bfs(int X) {
	int Y;
	memset(D, 0, sizeof(D));
	D[X] = 1;
	Q.push(X);
	while (Q.size()) {
		X = Q.front();
		Q.pop();
		for (int i = 0; i < Gr[X].size(); i++) {
			Y = Gr[X][i];
			if (!D[Y]) {
				D[Y] = D[X] + 1;
				Q.push(Y);
			}
		}
	}
	Y = X;
	for (int i = 1; i <= N; i++)
		if(D[i] > D[Y]) Y = i;
	return Y;	
}

int main() {
	int X, Y;

	freopen("darb.in","r",stdin);
	freopen("darb.out","w",stdout);
	
	scanf("%d", &N);
	for (int i = 1; i < N; i++) {
		scanf("%d %d", &X, &Y);
		Gr[X].push_back(Y);
		Gr[Y].push_back(X);
	}
	X = Bfs(1);
	X = Bfs(X);
	printf("%d\n", D[X]);

	return 0;
}