Mai intai trebuie sa te autentifici.
Cod sursa(job #2814377)
Utilizator | Data | 7 decembrie 2021 23:32:01 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.13 kb |
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMax 100001
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n;
class graf
{
int n;
vector <int> muchii[NMax];
public:
graf(int n);
void bfs_darb(int s, int &ultim, int &dist_max);
void darb();
};
graf :: graf(int n)
{
this->n = n;
}
void graf::bfs_darb(int s, int &ultim, int &dist_max) //am modificat primul bfs ca sa poata salva elem si dist pana la el
{
dist_max=0;
queue<int> q;
int vizitat[NMax];
int distanta[NMax];
for (int i = 0; i < n; i++)
{vizitat[i] = false;
distanta[i]=0;} //populeza vectorii si ii initializeaza ca si nevizitati
q.push(s); //adaugam in coada s-ul de start si il marcam ca vizitat si distanta 0
vizitat[s] = true;
distanta[s] = 1;
while (!q.empty()) //daca avem elemente in coada, executam:
{
int curent = q.front(); //nodul curent devine cel mai vechi nod adaugat in coada
q.pop();
//parcurgem lista de adicaneta pt a gasi varfurile adiacente nevizitate ale noduliui curent
for (auto i:muchii[curent])
{
if (!vizitat[i])
{
vizitat[i] = true;
q.push(i);
distanta[i] = distanta[curent] + 1;
if(distanta[i]>dist_max) //atunci cand gasim dist max salvam dist si elem
{
dist_max=distanta[i];
ultim=i;
}
}
}
}
}
void graf::darb(){
int start_node, end_node, distanta_maxima;
f >> n;
int nod1, nod2;
for(int i = 1; i <= n; ++i)
{
f >> nod1 >> nod2;
muchii[nod1].push_back(nod2);
muchii[nod2].push_back(nod1);
}
bfs_darb(1, start_node, distanta_maxima); //bfs de la nod 1 la prim din bfs final
bfs_darb(start_node, end_node, distanta_maxima); //bfs de la prim la ultimul nod din bfs final
g << distanta_maxima;
}
int main()
{
graf G(n);
G.darb();
return 0;
}