Pagini recente » Cod sursa (job #3123835) | Cod sursa (job #242935) | Cod sursa (job #256515) | Cod sursa (job #1605826) | Cod sursa (job #3272433)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <climits>
#define INFINIT INT_MAX
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
class Graf {
private:
int nrNoduri;
bool eOrientat, arePonderi;
vector<int> *adiacenta; // lista de vecini
vector<pair<int, pair<int, int>>> muchii; // {cost, {sursa, destinatie}};
public:
explicit Graf(int nrNoduri);
Graf(int nrNoduri, const bool eOrientat, const bool arePonderi);
void citire(const int nrMuchii);
void rezolvaBFS(int &nodPlecare);
void rezolvaDFS();
void rezolvaBiconex();
void rezolvaComponenteTareConexe(const int &nrMuchii);
void havelHakimi(const bool sortareCountingSort);
void rezolvaSortareTopologica();
void rezolvaMuchieCritica();
void rezolvaGrafInfoarena(int &nodStart, int &nodEnd);
void rezolvaAPM(int &nrMuchii);
void rezolvaDisjoint(int &nrMuchii);
void rezolvaDijkstra(int &nrMuchii);
void rezolvaBellmanFord(int &nrMuchii);
vector<vector<int>> royFloyd(vector<vector<int>> &matrice);
int rezolvaDiametruArbrore();
~Graf();
private:
void adaugaMuchie(const int sursa, const int destinatie);
void adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost);
vector<int> rezolvaBFS2(int nodPlecare);
void BFSrecursiv(queue<int> &coada, vector<int> &vizitat);
};
void Graf::BFSrecursiv(queue<int> &coada, vector<int> &vizitat) {
if (!coada.empty()) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
{
int nodPlecare = coada.front(); // retin nodul de unde plec
for (auto &i: adiacenta[nodPlecare])
if (vizitat[i] == -1) {
// caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
vizitat[i] = vizitat[nodPlecare] + 1; // il marcam vizitat
coada.push(i); // il adaug in coada PUSH
}
coada.pop();
BFSrecursiv(coada, vizitat);
}
}
vector<int> Graf::rezolvaBFS2(int nodPlecare) {
vector<int> vizitat(nrNoduri + 1, -1);
queue<int> coada;
coada.push(nodPlecare);
vizitat[coada.back()] = 1;
BFSrecursiv(coada, vizitat);
return vizitat;
}
int Graf::rezolvaDiametruArbrore() {
vector<int> distante = rezolvaBFS2(1);
int diametruMaxim = -1, ultimulNod;
for (int i = 1; i <= nrNoduri; i++)
if (distante[i] > diametruMaxim) {
diametruMaxim = distante[i];
ultimulNod = i;
}
distante = rezolvaBFS2(ultimulNod);
diametruMaxim = -1;
for (int i = 1; i <= nrNoduri; i++)
if (distante[i] > diametruMaxim)
diametruMaxim = distante[i];
return diametruMaxim;
}
int main() {
int nrNoduri;
fin >> nrNoduri;
Graf g1(nrNoduri, false, false);
g1.citire(nrNoduri);
fout << g1.rezolvaDiametruArbrore();
fin.close();
fout.close();
return 0;
}
Graf::Graf(const int nrNoduri) {
this->nrNoduri = nrNoduri;
}
Graf::Graf(const int nrNoduri, const bool eOrientat, const bool arePonderi) {
this->nrNoduri = nrNoduri;
this->eOrientat = eOrientat;
this->arePonderi = arePonderi;
}
void Graf::adaugaMuchie(const int sursa, const int destinatie) {
adiacenta[sursa].push_back(destinatie);
}
void Graf::adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost) {
// adiacentaCost[sursa].push_back(muchieCost(destinatie, cost));
}
void Graf::citire(const int nrMuchii) {
int sursa, destinatie; // extremitate muchie stanga respectiv dreapta
adiacenta = new vector<int>[nrNoduri + 1];
if (!arePonderi) {
if (eOrientat)
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie;
adaugaMuchie(sursa, destinatie);
}
else
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie;
adaugaMuchie(sursa, destinatie);
adaugaMuchie(destinatie, sursa);
}
} else {
int cost; // costul muchiei
muchii.resize(nrMuchii + 1);
if (eOrientat)
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie >> cost;
muchii[i] = {cost, {sursa, destinatie}};
}
else
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie >> cost;
muchii[i] = {cost, {sursa, destinatie}};
}
}
}
Graf::~Graf() {
delete[] adiacenta;
}