Cod sursa(job #1175362)

Utilizator sziliMandici Szilard szili Data 24 aprilie 2014 19:42:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

vector<int> **a;
int n;
int maxDiameter = -1;

void readData(){
	scanf("%d", &n);
	a = new vector<int> *[n+1];

	for (int i=1; i<=n; i++){
		a[i] = new vector<int>();
	}

	for (int i=0; i<n-1; i++){
		int parent, child;

		scanf("%d %d", &parent, &child);
		a[parent]->push_back(child);
	}
}

int findDiameter(int current){

	int heightMax = -1;
	int heightNextMax = -1;

	for (int i=0; i<a[current]->size(); i++){
		int height = findDiameter((*a[current])[i]);

		if (height > heightMax){
			heightNextMax = heightMax;
			heightMax = height;
		} else if (height > heightNextMax){
			heightNextMax = height;
		}
	}

	if (heightMax + heightNextMax + 2 > maxDiameter){
		maxDiameter = heightMax + heightNextMax + 2;
	}

	return heightMax + 1;
}

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

	readData();

	findDiameter(1);

	printf("%d", maxDiameter+1);
}