Cod sursa(job #2469662)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 7 octombrie 2019 20:19:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int const maxim = 100005;
int distanta[maxim];
int n;
int maxim1 = 0, maxim2 = 0;
int nod1 = 0, nod2 = 0;
vector <int>  stocare[maxim];
queue <int> coada;
bool okay = true;

void citire() {
	ifstream in("darb.in");
	in >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		in >> a >> b;
		stocare[a].push_back(b);
		stocare[b].push_back(a);
	}
	in.close();
}

void bfs() {
	int nod, vecin;
	while (!coada.empty()) {
		nod = coada.front();
		coada.pop();
		for (size_t i = 0; i < stocare[nod].size(); i++) {
			vecin = stocare[nod][i];
			if (distanta[vecin] == -1) {
				distanta[vecin] = distanta[nod] + 1;
				if (okay) {
					if (distanta[vecin] > maxim1) {
						maxim1 = distanta[vecin];
						nod1 = vecin;
					}
				}
				else {
					if (distanta[vecin] > maxim2) {
						maxim2 = distanta[vecin];
						nod2 = vecin;
					}
				}
				coada.push(vecin);
			}
		}
	}
}

void diametru() {
	for (int i = 1; i <= n; i++) {
		distanta[i] = -1;
	}
	distanta[1] = 1;
	coada.push(1);
	bfs();

	okay = false;
	for (int i = 1; i <= n; i++) {
		distanta[i] = -1;
	}
	distanta[nod1] = 1;
	coada.push(nod1);
	bfs();

	ofstream out("darb.out");
	out << maxim2;
	out.close();
}

int main()
{
	citire();
	diametru();
	return 0;
}