Cod sursa(job #2811661)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 2 decembrie 2021 20:14:07
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

class Graf {
	int noduri, muchii;
	vector<vector<int>>vecini;
	vector<bool>vizitat;

public:
	Graf(int n);
	void adauga_muchie_neorientat(int nod1, int nod2);
	void diametrul_unui_arbore();
	void dfs_diametrul_unui_arbore(int nod, int nivel_curent, int& nivel_max, int& poz_niv_max);
};

Graf::Graf(int n)
{
	this->noduri = n;
	this->muchii = 0;

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1);

	for (int i = 1; i <= n; i++)
		vizitat[i] = 0;
}

void Graf::adauga_muchie_neorientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini[nod2].push_back(nod1);
}

void Graf::diametrul_unui_arbore()
{
	for (int i = 1; i < noduri; i++)
	{
		int st, dr;

		f >> st >> dr;

		adauga_muchie_neorientat(st, dr);
	}

	int nivel_max = 0, poz_niv_max = 0;

	dfs_diametrul_unui_arbore(1, 0, nivel_max, poz_niv_max);

	for (int i = 1; i <= noduri; i++)
		vizitat[i] = 0;

	//cout << nivel_max << " " << poz_niv_max << "\n";

	dfs_diametrul_unui_arbore(poz_niv_max, 0, nivel_max, poz_niv_max);

	o << nivel_max + 1;
}

void Graf::dfs_diametrul_unui_arbore(int nod, int nivel_curent, int& nivel_max, int& poz_niv_max)
{
	vizitat[nod] = 1;

	if (nivel_curent > nivel_max)
	{
		nivel_max = nivel_curent;
		poz_niv_max = nod;
	}

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			dfs_diametrul_unui_arbore(*i, nivel_curent + 1, nivel_max, poz_niv_max);
}

int main()
{
	int N;

	f >> N;

	Graf g(N);

	g.diametrul_unui_arbore();

	return 0;
}