Cod sursa(job #1247946)

Utilizator adysnookAdrian Munteanu adysnook Data 24 octombrie 2014 12:53:11
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <unordered_set>
#include <vector>
#include <queue>

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

struct nod{
	int x;
	unordered_set<int> legaturi;
};

int main(){
	int n, i, x, y;
	in >> n;
	vector<bool> viz(n + 1);
	vector<nod> noduri(n + 1);
	for (i = 0; i < n; ++i){
		in >> x >> y;
		noduri[x].legaturi.insert(y);
		noduri[y].legaturi.insert(x);
	}
	queue<int> coada;
	coada.push(1);
	int q;
	while (!coada.empty()){
		q = coada.front();
		coada.pop();
		viz[q] = true;
		for (auto next : noduri[q].legaturi){
			if (!viz[next])
				coada.push(next);
		}
	}
	for (i = 1; i <= n; ++i){
		viz[i] = false;
	}
	unordered_set<int> coadax, temp;
	coadax.insert(q);
	int k = 0, vizt = 0;
	while (vizt != n){
		++k;
		temp.clear();
		for (auto c : coadax){
			viz[c] = true;
			++vizt;
			for (auto next : noduri[c].legaturi){
				if (!viz[next])
					temp.insert(next);
			}
		}
		coadax.swap(temp);
	}
	out << k;
	return 0;
}