Cod sursa(job #1278791)

Utilizator evodaniVasile Daniel evodani Data 29 noiembrie 2014 14:15:01
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
FILE *fin, *fout;

#define NMAX 100005

bool visited [NMAX];

void dfs (vector < vector<int> > &arb, int node, int depth, int &maxDepth, int &leafMax) {
	int i;
	visited[node]=1;
	for (i=0; i<arb[node].size(); ++i) if (!visited[arb[node][i]])
		dfs (arb, arb[node][i], depth+1, maxDepth, leafMax);
 	if (depth > maxDepth) {
		maxDepth = depth;
		leafMax = node;
	}
}

int main() {
	fin = fopen ("darb.in", "r");
	fout = fopen ("darb.out", "w");

	int n, i, a, b, maxDepth = 0, leafMax;
	fscanf (fin, "%d", &n);
	vector < vector<int> > arb (n+1);

	for (i=1; i<n; ++i) {
		fscanf (fin, "%d%d", &a, &b);
		arb[a].push_back(b);
		arb[b].push_back(a);
	}

	dfs (arb, 1, 1, maxDepth, leafMax);

	memset (visited, 0, sizeof (bool) * (n+1));
	maxDepth = 0;

	dfs (arb, leafMax, 1, maxDepth, leafMax);

	fprintf (fout, "%d\n", maxDepth);

	fclose (fin); fclose(fout);
	return 0;
}