Cod sursa(job #1223095)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 25 august 2014 14:20:38
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
#include<vector>
#include<string.h>
#define Nmax 100010
using namespace std;

vector<int> G[Nmax];
int N, diam, dist[Nmax], x, y;


void dfs(int nod, int depth) {

	dist[nod] = depth;
	if (depth > diam) diam = depth;
	for(vector<int> :: iterator it = G[nod].begin() ; it != G[nod].end() ; it++)
		if (!dist[*it]) dfs(*it, depth+1);
}


int main() {

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

	dfs(1, 1);
	for (int i = 1 ; i <= N ; i++)
		if (dist[i] == diam) {
			memset(dist, 0, sizeof(dist));
			dfs(i, 1);
			break;
		}

	printf("%d\n", diam);
	return 0;
}