Cod sursa(job #1470529)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 11 august 2015 16:49:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <cstring>
#include <vector>

#define maxdim 100005

using namespace std;

int n;
int D[maxdim];
vector<int> G[maxdim];

void dfs(int nod) {

	for (int son : G[nod]) {
		if (D[son] == 0) {
			D[son] = D[nod] + 1;
			dfs(son);
		}
	}
}

inline int getMostDistant() {

	int mostDistant = 0;
	for (int i = 1; i <= n; ++i) {
		if (D[i] > D[mostDistant]) {
			mostDistant = i;
		}
	}

	return mostDistant;
}

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);
		G[x].push_back(y);
		G[y].push_back(x);
	}

	D[1] = 1;
	dfs(1);
	
	int next_start = getMostDistant();
	memset(D, 0, sizeof(D));
	D[next_start] = 1;
	dfs(next_start);

	int diameter = 0;
	for (int i = 1; i <= n; ++i) {
		if (D[i] > diameter) {
			diameter = D[i];
		}
	}

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

	return 0;
}