Pagini recente » Cod sursa (job #2639574) | Cod sursa (job #1007521) | Cod sursa (job #460691) | Cod sursa (job #224308) | Cod sursa (job #2811661)
#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;
}