Cod sursa(job #1247736)

Utilizator adysnookAdrian Munteanu adysnook Data 23 octombrie 2014 15:51:03
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 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;
	}
	int l = 0;
	queue<pair<int, int>> coada2;
	coada2.push(make_pair(q, 1));
	pair<int, int> q2;
	while (!coada2.empty()){
		q2 = coada2.front();
		coada2.pop();
		viz[q2.first] = true;
		for (auto next : noduri[q2.first].legaturi){
			if (!viz[next])
				coada2.push(make_pair(next, q2.second+1));
		}
	}
	out << q2.second;
	return 0;
}