Cod sursa(job #1451090)

Utilizator astronoviceAlexandru Pana astronovice Data 15 iunie 2015 23:33:30
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

static const int MAX_SIZE = 100000;

std::vector<int> nod[MAX_SIZE];
int tsize;
int diameter;

void readTree() {
	ifstream fin("darb.in");

	fin >> tsize;

	for (int i = 0; i < tsize; ++i) {
		int a, b;
		fin >> a >> b;
		nod[a].push_back(b);
		nod[b].push_back(a);
	}
	
	fin.close();
}

int bfs(int root) {
	std::queue<int> queue;
	bool *vizited = new bool[tsize+1];
	int *depth = new int[tsize+1];

	memset(vizited, 0, sizeof(bool) * (tsize + 1));
	memset(depth, 0, sizeof(int) * (tsize + 1));

	queue.push(root);
	vizited[root] = 1;
	depth[root] = 1;
	int el;

	while (!queue.empty()) {
		el = queue.front();
		queue.pop();
		for (int& i : nod[el]) {
			if (!vizited[i]) {
				vizited[i] = 1;

				queue.push(i);
				depth[i] = depth[el] + 1;
				diameter = depth[i];
			}
		}
	}

	return el;
}

int main() {
	readTree();

	int l = bfs(1);
	bfs(l);

	ofstream fout("darb.out");
	fout << diameter;

	fout.close();
	return 0;
}