Cod sursa(job #1208188)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 14 iulie 2014 23:17:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;

vector<int> graph[100005];
bool viz[100005];
int start, endd;
int nrMuchii;
int diametru;
int nodFinalPrimulLant;

void dfs(int node, int nivel)
{
	if(nivel + 1 > diametru)
	{
		diametru = nivel + 1;
		nodFinalPrimulLant = node;
	}
	
	viz[node] = true;

	for(int i = 0; i < graph[node].size(); ++i)
	{
		if(!viz[graph[node][i]])
			dfs(graph[node][i], nivel+1);
	}
}

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

	scanf("%d", &nrMuchii);
	for(int i = 0; i < nrMuchii; ++i)
	{
		scanf("%d%d", &start, &endd);
		graph[start].push_back(endd);
		graph[endd].push_back(start);
	}

	diametru = 0;

	dfs(1, 0);

	memset(viz, false, sizeof(viz));

	dfs(nodFinalPrimulLant, 0);

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

	return 0;
}