Cod sursa(job #2417820)

Utilizator ElChapo77Nacu Florin ElChapo77 Data 1 mai 2019 17:02:07
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<list>
using namespace std;

void citire(vector<list<unsigned>>& arbore)
{
	ifstream f("darb.in");
	unsigned n;
	f >> n;
	arbore.resize(n);
	for (unsigned i = 0; i < n - 1; i++)
	{
		unsigned x, y;
		f >> x >> y;
		arbore[x - 1].push_back(y);
		arbore[y - 1].push_back(x);
	}
	f.close();
}

unsigned bf(const vector<list<unsigned>>& arbore, const unsigned& start, unsigned& finish)
{
	vector<unsigned> tata(arbore.size(), arbore.size() + 1);
	vector<bool> viz(arbore.size(), false);
	queue<unsigned> coada;
	coada.push(start);
	viz[start - 1] = true;
	
	while (coada.size() > 0)
	{
		finish = coada.front();
		coada.pop();
		for (auto i : arbore[finish - 1])
			if (viz[i - 1] == false)
			{
				coada.push(i);
				viz[i - 1] = true;
				tata[i - 1] = finish;
			}
	}

	unsigned diametru = 0;
	unsigned x = finish;
	diametru = 1;
	while (x != start)
	{
		x = tata[x - 1];
		diametru++;
	}

	return diametru;
}

int main()
{
	vector<list<unsigned>> arbore;
	citire(arbore);
	unsigned nod1 = 0;
	unsigned nod2 = 0;
	bf(arbore, 1, nod1);
	unsigned diametru = bf(arbore, nod1, nod2);

	ofstream g("darb.out");
	g << diametru;
	g.close();
}