Cod sursa(job #2198113)

Utilizator SirStevensIonut Morosan SirStevens Data 23 aprilie 2018 17:44:40
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
// Centru_Diam.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

vector <int> la[100001];
deque <int> Q;

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

void BF(int node, int *&tata, int *&viz, int*&L) {
	int val;
	L[node] = 0;
	Q.push_back(node);
	while (!Q.empty()) {
		val = Q.front();
		Q.pop_front();
		for (int i = 0; i < la[val].size(); i++) {
			if (!viz[la[val][i]]) {
				viz[la[val][i]] = 1;
				Q.push_back(la[val][i]);
				tata[la[val][i]] = val;
				L[la[val][i]]= L[val] + 1;
			}
		}
	}

}


void read() {
	int n, m, x, y;
	in >> n;
	int *viz = new int[100001], *tata = new int[100001], *L = new int[100001];
	for (int i = 1; i <= 100000; i++) {
		viz[i] = tata[i] = 0;
		L[i] = -1;
	}
	for (int i = 1; i < n; i++) {
		in >> x >> y;
		la[x].push_back(y);
		la[y].push_back(x);
	}
	BF(1, tata, viz, L);
	int max = 0, idx = 1;
	for (int i = 2; i <= n; i++)
		if (L[i] > max)
		{
			max = L[i];
			idx = i;
		}
	for (int i = 1; i <= 100000; i++) {
		viz[i] = tata[i] = 0;
		L[i] = -1;
	}
	BF(idx, tata, viz, L);
	for (int i = 2; i <= n; i++)
		if (L[i] > max)
		{
			max = L[i];
			idx = i;
		}
	out << idx <<'\n';
	delete tata;
	delete viz;
	delete L;
}



int main()
{
	read();
    return 0;
}