#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;
const int nul = -1;
const int maxim = 1000000;
class Graf
{
int nr_noduri;
int nr_muchii;
vector<vector<int>> lista_adiacenta;
void DFS(int nod, vector<bool>& vizitat);
//functie apelata din componente_conexe care face algoritmul de DFS pe
//un graf dat
void gasire_componenta_biconexa(int nod1, int nod2, vector<vector<int>>& comp_biconexe, stack<pair<int, int>>& muchii_comp_biconexe);
//functie apelata din componente_biconexe care creeaza un vector de muchii
//(componenta biconexa neprelucrata) si il pune in vectorul de
//componente biconexe
void DFS_tare_conexe(int nod, int& index_ctc, vector<int>& index, vector<int>& low, vector<bool>& inComponenta, stack<int>& noduri_comp_tare_conexa, vector<vector<int>>& comp_tare_conexe);
//functie apelata din componente_tare_conexe care cauta componente tare
//conexe si le pune intr-un vector
void DFS_muchii_critice(int nod, vector<int>& nivel, vector<int>& low, vector<vector<int>>& lista_muchii);
//functie apelata din muchii_critice care cauta muchii critice si le pune
//intr-un vector de muchii
int reprez_Kruskal(int nod, vector<int>& tata);
//functie apelata din apm_Kruskal care gaseste reprezentantul unui nod dat
void reunire_Kruskal(int nod1, int nod2, vector<int>& tata, vector<int>& inaltime);
//functie apelata din apm_Kruskal care face reuniunea componentelor a doua
//noduri date
int reprez_paduri(int nod, vector<int>& tata);
//functie apelata din paduri_disjuncte care gaseste reprezentantul unui
//nod dat
void reunire_multimi_paduri(int nod1, int nod2, vector<int>& tata, vector<int>& inaltime);
//functie apelata din paduri_disjuncte care face reuniunea componentelor
//a doua noduri date
public:
Graf();
void citire_neorientat(const string fis);
void citire_orientat(const string fis);
int citire_orientat_bfs(const string fis);
//functie de citire specifica problemei BFS
//pentru a permite citirea nodului de start
vector<vector<int>> citire_neorientat_cost(const string fis);
vector<vector<pair<int, int>>> citire_orientat_cost(const string fis);
vector<int> BFS(int nod_start);
//functie care face algoritmul de BFS pe un graf pornind de la un nod de
//start dat
int componente_conexe();
//functie care foloseste DFS pentru a gasi cate componente conexe sunt
//intr-un graf
void componente_biconexe(int nod_curent, int nod_initial, int nv, vector<int>& nivel, vector<int>& low, vector<vector<int>>& comp_biconexe, stack<pair<int, int>>& muchii_comp_biconexe);
//functie care cauta componentele biconexe dintr-un graf
vector<vector<int>> componente_tare_conexe();
//functie care incepe un algoritm de cautare a componentelor tare conexe
//si care returneaza un vector cu aceste componente
void havel_hakimi(vector<int>& secv_grade, int n, const string fis);
//functie care ia ca argument o secventa de grade si spune daca se poate
//construi un graf cu aceste grade folosind algoritmul Havel-Hakimi
vector<int> sort_top();
//functie care returneaza sortarea topologica a unui graf orientat
vector<vector<int>> muchii_critice();
//functie csre incepe un algoritm de cautare a muchiilor critice si care
//returneaza vectorul cu aceste muchii
vector<vector<int>> apm_Kruskal(vector<vector<int>>& muchii_ponderate, int& cost_apm);
//functie care ia un vector de muchii cu costuri ale unui graf. Ea va
//returna APM pentru graful dat si va modifica variabila cost_apm astfel
//incat sa stocheze costul APM-ului cerut
void paduri_disjuncte(const string fis_in, const string fis_out);
//functie care efectueaza operatii de reuniune de multimi si de
//aflare a egalitatii reprezentantilor a doua noduri date
vector<int> dijkstra(vector<vector<pair<int, int>>>& muchii_ponderate);
//functie care ia un vector de muchii cu costuri pentru fiecare nod
//(pozitive). Ea returneaza un vector care reprezinta distantele de la
//nodul 1 la celelalte noduri
vector<int> bellman_ford(vector<vector<pair<int, int>>>& muchii_ponderate);
//functie care ia un vector de muchii cu costuri pentru fiecare nod. Ea
//returneaza un vector care reprezinta distantele de la nodul 1 la
//celelalte noduri
bool verif_ciclu_bellman_ford(vector<vector<pair<int, int>>>& muchii_ponderate, vector<int>& distanta, const string fis);
//functie care verifica pentru un graf asupra caruia s-a aplicat
//algoritmul Bellman-Ford daca prezinta cicluri negative; returneaza true
//daca s-a gasit cel putin un astfel de ciclu, si false altfel
};
Graf::Graf(){
nr_noduri = 0;
nr_muchii = 0;
}
void Graf::citire_neorientat(const string fis){
ifstream fi(fis);
fi >> nr_noduri >> nr_muchii;
for (int i = 1; i <= nr_noduri + 1; i++){
lista_adiacenta.push_back(vector<int>());
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2;
fi >> nod_1 >> nod_2;
lista_adiacenta[nod_1].push_back(nod_2);
lista_adiacenta[nod_2].push_back(nod_1);
}
fi.close();
}
void Graf::citire_orientat(const string fis){
ifstream fi(fis);
fi >> nr_noduri >> nr_muchii;
for (int i = 1; i <= nr_noduri + 1; i++){
lista_adiacenta.push_back(vector<int>());
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2;
fi >> nod_1 >> nod_2;
lista_adiacenta[nod_1].push_back(nod_2);
}
fi.close();
}
int Graf::citire_orientat_bfs(const string fis){
ifstream fi(fis);
int nod_start;
fi >> nr_noduri >> nr_muchii >> nod_start;
for (int i = 1; i <= nr_noduri + 1; i++){
lista_adiacenta.push_back(vector<int>());
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2;
fi >> nod_1 >> nod_2;
lista_adiacenta[nod_1].push_back(nod_2);
}
fi.close();
return nod_start;
}
vector<vector<int>> Graf::citire_neorientat_cost(const string fis){
vector<vector<int>> muchii_ponderate;
ifstream fi(fis);
fi >> nr_noduri >> nr_muchii;
for (int i = 1; i <= nr_noduri + 1; i++){
lista_adiacenta.push_back(vector<int>());
}
for (int i = 0; i < nr_muchii; i++){
muchii_ponderate.push_back(vector<int>());
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2, cost;
fi >> nod_1 >> nod_2 >> cost;
lista_adiacenta[nod_1].push_back(nod_2);
lista_adiacenta[nod_2].push_back(nod_1);
//punem datele citite in forma [cost, nod_1, nod_2] ca sa nu fie
//nevoie de un criteriu de sort (se va face o sortare directa dupa
//primul element)
muchii_ponderate[i].push_back(cost);
muchii_ponderate[i].push_back(nod_1);
muchii_ponderate[i].push_back(nod_2);
}
fi.close();
return muchii_ponderate;
}
vector<vector<pair<int, int>>> Graf::citire_orientat_cost(const string fis){
//retinem muchiile cu costuri ca un vector de vectori de perechi de forma
//muchii_ponderate[nod_1] -> (nod_2, cost) pentru a gasi eficient muchiile
//necesare
vector<vector<pair<int, int>>> muchii_ponderate;
ifstream fi(fis);
fi >> nr_noduri >> nr_muchii;
for (int i = 1; i <= nr_noduri + 1; i++){
lista_adiacenta.push_back(vector<int>());
}
for (int i = 1; i <= nr_noduri + 1; i++){
muchii_ponderate.push_back(vector<pair<int, int>>());
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2, cost;
fi >> nod_1 >> nod_2 >> cost;
lista_adiacenta[nod_1].push_back(nod_2);
muchii_ponderate[nod_1].push_back(make_pair(nod_2, cost));
}
fi.close();
return muchii_ponderate;
}
vector<int> Graf::BFS(int nod_start){
//declaram si initializam un vector "vizitat" pentru marcarea nodurilor
//vizitate, o coada "coada_varfuri" pentru prelucrarea in ordine a
//nodurilor parcurse, un vector "nivel" care stocheaza nivelurile pe care
//se afla fiecare nod si o variabila "nod" pentru nodul care trebuie
//prelucrat
vector<bool> vizitat(nr_noduri + 1, false);
queue<int> coada_varfuri;
vector<int> nivel(nr_noduri + 1, nul);
//incepem prin a pune nodul de start in coada, marcandu-l drept vizitat
//si setandu-i nivelul ca fiind 0
coada_varfuri.push(nod_start);
vizitat[nod_start] = true;
nivel[nod_start] = 0;
//facem BFS pana cand nu mai sunt noduri de prelucrat
while (!coada_varfuri.empty()){
//luam un nod din coada
int nod = coada_varfuri.front();
//pentru fiecare vecin al sau
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
//daca vecinul respectiv nu a mai fost vizitat, il punem in
//coada, il marcam drept vizitat si ii setam nivelul ca fiind
//cel al nodului initial + 1
if (!vizitat[*i]){
coada_varfuri.push(*i);
vizitat[*i] = true;
nivel[*i] = nivel[nod] + 1;
}
}
//eliminam nodul din coada
coada_varfuri.pop();
}
return nivel;
}
void Graf::DFS(int nod, vector<bool>& vizitat){
//marcam nodul curent ca fiind vizitat
vizitat[nod] = true;
//pentru fiecare vecin al sau
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
//daca vecinul respectiv nu a mai fost vizitat, apelam DFS pe acesta
if (!vizitat[*i]){
DFS(*i, vizitat);
}
}
}
int Graf::componente_conexe(){
//declaram si initializam un vector "vizitat" pentru marcarea nodurilor
//vizitate si o variabila "nr_comp_conexe" in care stocam numarul de
//componente conexe gasite (egal cu numarul de DFS-uri apelate din
//aceasta functie)
vector<bool> vizitat(nr_noduri + 1, false);
int nr_comp_conexe = 0;
//luam fiecare nod, si daca nu a mai fost vizitat, apelam DFS pornind
//de la el si incrementam numarul de componente conexe gasite
for (int i = 1; i <= nr_noduri; i++){
if (!vizitat[i]){
nr_comp_conexe++;
DFS(i, vizitat);
}
}
//la sfarsit, afisam numarul de componente conexe cerut
return nr_comp_conexe;
}
void Graf::gasire_componenta_biconexa(int nod1, int nod2, vector<vector<int>>& comp_biconexe, stack<pair<int, int>>& muchii_comp_biconexe){
//eliminam muchii din stiva pana ajungem la muchia (nod1, nod2)
//cream un vector in care retinem componenta biconexa (muchiile sale,
//mai tarziu vom pastra doar nodurile)
vector<int> comp;
int n1, n2;
do {
n1 = muchii_comp_biconexe.top().first;
n2 = muchii_comp_biconexe.top().second;
comp.push_back(n1);
comp.push_back(n2);
//stergem muchia din stiva
muchii_comp_biconexe.pop();
} while (n1 != nod1 && n2 != nod2);
//punem componenta in lista de componente
comp_biconexe.push_back(comp);
}
void Graf::componente_biconexe(int nod_curent, int nod_initial, int nv, vector<int>& nivel, vector<int>& low, vector<vector<int>>& comp_biconexe, stack<pair<int, int>>& muchii_comp_biconexe){
//setam adancimea si low[nod_curent]; initial, nodul curent are low
//egal cu adancimea
if (nivel.empty() && low.empty()){
for (int i = 1; i <= nr_noduri + 1; i++){
nivel.push_back(nul);
low.push_back(nul);
}
}
nivel[nod_curent] = nv;
low[nod_curent] = nv;
//pentru fiecare vecin al nodului
for (auto i = lista_adiacenta[nod_curent].begin(); i != lista_adiacenta[nod_curent].end(); i++){
//daca intalnim nodul initial printre vecini, il ignoram
if (*i == nod_initial){
continue;
}
//daca intalnim un nod pe care nu l-am vizitat
if (nivel[*i] == nul){
//punem muchia dintre cele doua noduri in stiva
muchii_comp_biconexe.push(make_pair(nod_curent, *i));
//apelam DFS (reapelam aceasta functie) pe nodul gasit
//nv va avea valoarea nv + 1
componente_biconexe(*i, nod_curent, nv + 1, nivel, low, comp_biconexe, muchii_comp_biconexe);
//dupa ce iesim din recursie, va trebui sa actualizam
//low[nod_curent] cu low-ul nodului gasit
low[nod_curent] = min(low[nod_curent], low[*i]);
//daca nodul gasit nu poate ajunge la un stramos al nodului curent
if (low[*i] >= nivel[nod_curent]){
//am gasit o componenta biconexa, deci incepem sa o retinem
gasire_componenta_biconexa(nod_curent, *i, comp_biconexe, muchii_comp_biconexe);
}
} else {
//altfel, actualizam low[nod_curent] cu adancimea nodului gasit
low[nod_curent] = min(low[nod_curent], nivel[*i]);
}
}
}
void Graf::DFS_tare_conexe(int nod, int& index_ctc, vector<int>& index, vector<int>& low, vector<bool>& inComponenta, stack<int>& noduri_comp_tare_conexa, vector<vector<int>>& comp_tare_conexe){
//initializam nodul si low[nod] cu index-ul curent, punem nodul in stiva,
//ii marcam prezenta in stiva si setam indexul pentru urmatorul nod
index[nod] = index_ctc;
low[nod] = index_ctc;
index_ctc++;
noduri_comp_tare_conexa.push(nod);
inComponenta[nod] = true;
//pentru fiecare vecin al nodului
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
//daca nodul nu a fost vizitat, apelam DFS pe acest nod si actualizam
//low-ul nodului curent cu low-ul nodului gasit
if (index[*i] == nul){
DFS_tare_conexe(*i, index_ctc, index, low, inComponenta, noduri_comp_tare_conexa, comp_tare_conexe);
low[nod] = min(low[nod], low[*i]);
} else if (inComponenta[*i]){
//altfel, daca nodul este in stiva (si deci in componenta curenta),
//actualizam low-ul nodului curent cu indexul nodului gasit
low[nod] = min(low[nod], index[*i]);
}
}
//daca low-ul unui nod este egal cu indexul sau, atunci inseamna ca el e
//nodul "radacina" si ca trebuie sa formam componenta tare conexa din
//acest nod
if (low[nod] == index[nod]){
//cream vectorul cu nodurile din componenta tare conexa extragandu-le
//din stiva si stergandu-le prezenta in stiva; adaugam apoi acest
//vector printre componente
vector<int> comp;
int n;
do {
n = noduri_comp_tare_conexa.top();
comp.push_back(n);
inComponenta[n] = false;
noduri_comp_tare_conexa.pop();
} while (n != nod);
comp_tare_conexe.push_back(comp);
}
}
vector<vector<int>> Graf::componente_tare_conexe(){
int index_ctc = 0;
vector<int> index(nr_noduri + 1, nul);
vector<int> low(nr_noduri + 1, nul);
vector<bool> inComponenta(nr_noduri + 1, false);
stack<int> noduri_comp_tare_conexa;
vector<vector<int>> comp_tare_conexe;
for (int i = 1; i <= nr_noduri; i++){
if (index[i] == nul){
DFS_tare_conexe(i, index_ctc, index, low, inComponenta, noduri_comp_tare_conexa, comp_tare_conexe);
}
}
return comp_tare_conexe;
}
void Graf::havel_hakimi(vector<int>& secv_grade, int n, const string fis){
//declaram o variabila suma_grade pentru a verifica daca suma gradelor
//este para sau nu
int suma_grade = 0;
ofstream fo(fis);
for (int i = 0; i < n; i++){
//verificam daca un grad este mai mare decat n, daca da atunci
//nu se poate construi graful cerut
if (secv_grade[i] > n - 1){
fo << "NU";
fo.close();
return;
}
//altfel, adunam gradul la suma pentru a doua conditie necesara
suma_grade += secv_grade[i];
}
//daca suma gradelor este impara, nu se poate construi graful cerut
if (suma_grade % 2 != 0){
fo << "NU";
fo.close();
return;
}
//sortam descrescator vectorul de grade pentru a alege cel mai mare grad
//din secventa
sort(secv_grade.begin(), secv_grade.end(), greater<int>());
//algoritmul ruleaza cat timp secventa contine valori nenule
//vectorul fiind sortat descrescator, daca primul element este nul,
//inseamna ca si celelalte elemente sunt nule
while (secv_grade[0] > 0){
//scadem gradele pentru atatea noduri cat este gradul nodului curent
for (int i = 1; i <= secv_grade[0]; i++){
secv_grade[i]--;
//daca un nod, prin aceasta scadere, ajunge sa aiba grad negativ,
//atunci nu se poate construi graful cerut
if (secv_grade[i] < 0){
fo << "NU";
fo.close();
return;
}
}
//eliminam gradul prelucrat
secv_grade.erase(secv_grade.begin());
//sortam din nou vectorul descrescator pentru a alege, in continuare,
//cel mai mare grad din secventa
sort(secv_grade.begin(), secv_grade.end(), greater<int>());
}
//daca programul nu a fost intrerupt pana acum, inseamna ca putem construi
//graful cerut
fo << "DA";
fo.close();
}
vector<int> Graf::sort_top(){
//declaram un vector grade_interne care stocheaza gradul intern al
//fiecarui nod, si punem lungimea listei de adiacenta intr-o variabila
vector<int> grade_interne(nr_noduri + 1, 0);
int lungime_lista_ad = lista_adiacenta.size();
//cream vectorul de grade interne luand toate muchiile din lista de
//adiacenta
for (int i = 1; i <= lungime_lista_ad; i++){
for (auto j = lista_adiacenta[i].begin(); j != lista_adiacenta[i].end(); j++){
grade_interne[*j]++;
}
}
//declaram o coada care stocheaza nodurile de prelucrat (ca la BFS)
//initial, punem in coada nodurile cu gradul intern 0
queue<int> coada_varfuri;
for (int i = 1; i <= nr_noduri + 1; i++){
if (grade_interne[i] == 0){
coada_varfuri.push(i);
}
}
//declaram vectorul sortare, care stocheaza sortarea topologica ceruta
vector<int> sortare;
//procesarea nodurilor are loc cat timp exista noduri in coada
while (!coada_varfuri.empty()){
//preluam un nod din coada, il adaugam in sortare si apoi il
//stergem din coada
int nod = coada_varfuri.front();
sortare.push_back(nod);
coada_varfuri.pop();
//parcurgem toate muchiile care pornesc din nodul respectiv si
//scadem gradul intern al nodurilor legate de acesta
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
grade_interne[*i]--;
//daca gradul intern al unui nod ajunge 0 prin aceasta scadere,
//introducem nodul in coada
if (grade_interne[*i] == 0){
coada_varfuri.push(*i);
}
}
}
return sortare;
}
void Graf::DFS_muchii_critice(int nod, vector<int>& nivel, vector<int>& low, vector<vector<int>>& lista_muchii){
//daca nivelul nodului curent este nul, inseamna ca acesta este primul
//apel al functiei, deci initializam acest nivel cu 0
if (nivel[nod] == nul){
nivel[nod] = 0;
}
//initial, low[nod] este egal cu nivelul nodului
low[nod] = nivel[nod];
//parcurgem muchiile care pornesc din acest nod
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
//daca am gasit un nod nevizitat
if (nivel[*i] == nul){
//initializam nivelul nodului pe care urmeaza sa apelam DFS cu
//nivelul nodului initial + 1
nivel[*i] = nivel[nod] + 1;
//apelam DFS pe nodul respectiv
DFS_muchii_critice(*i, nivel, low, lista_muchii);
//dupa apelul recursiv, verificam daca nodul gasit a putut urca
//mai sus de nodul initial; daca nu, am gasit o muchie critica
//pe care o punem in vectorul de muchii
if (low[*i] > nivel[nod]){
vector<int> muchie;
muchie.push_back(nod);
muchie.push_back(*i);
lista_muchii.push_back(muchie);
}
//deoarece nodul curent poate urca la acelasi nivel ca nodul
//gasit mergand in jos, actualizam low[nod] cu low-ul celui gasit
low[nod] = min(low[nod], low[*i]);
}
else if (nivel[*i] < nivel[nod] - 1){
//daca am gasit un nod vizitat care se afla mai sus de nodul
//curent, am gasit o muchie de intoarcere si actualizam low[nod]
//cu nivelul nodului gasit
low[nod] = min(low[nod], nivel[*i]);
}
}
}
vector<vector<int>> Graf::muchii_critice(){
//declaram un vector "nivel" care stocheaza nivelele la care se afla
//nodurile, un vector "low" care stocheaza cat de sus poate merge un nod
//printr-o muchie de intoarcere si un vector "lista_muchii" care
//stocheaza muchiile cerute
vector<int> nivel(nr_noduri + 1, nul);
vector<int> low(nr_noduri + 1, nul);
vector<vector<int>> lista_muchii;
//apelam DFS pe nodul de start 0
DFS_muchii_critice(0, nivel, low, lista_muchii);
return lista_muchii;
}
int Graf::reprez_Kruskal(int nod, vector<int>& tata){
while (tata[nod] != 0){
nod = tata[nod];
}
return nod;
}
void Graf::reunire_Kruskal(int nod1, int nod2, vector<int>& tata, vector<int>& inaltime){
int repr_nod1 = reprez_Kruskal(nod1, tata);
int repr_nod2 = reprez_Kruskal(nod2, tata);
//legam componenta cu inaltimea mai mica de cea cu inaltimea mai mare
//daca ambele componente au aceeasi inaltime, inaltimea componentei finale
//va creste cu 1
if (inaltime[repr_nod1] > inaltime[repr_nod2]){
tata[repr_nod2] = repr_nod1;
} else {
tata[repr_nod1] = repr_nod2;
if (inaltime[repr_nod1] == inaltime[repr_nod2]){
inaltime[repr_nod2]++;
}
}
}
vector<vector<int>> Graf::apm_Kruskal(vector<vector<int>>& muchii_ponderate, int& cost_apm){
//declaram un vector de tati si un vector de inaltimi, pentru reuniuni si
//gasiri de reprezentanti eficiente
vector<int> tata(nr_noduri + 1, 0);
vector<int> inaltime(nr_noduri + 1, 0);
vector<vector<int>> apm;
for (int i = 1; i < nr_noduri; i++){
apm.push_back(vector<int>());
}
//sortam muchiile dupa cost (deoarece elementele de indice 0 sunt
//costurile, nu este nevoie de un criteriu de sort)
sort(muchii_ponderate.begin(), muchii_ponderate.end());
//declaram o variabila care spune cate muchii am selectat pana acum
int muchii_selectate = 0;
for (int i = 0; i < nr_muchii; i++){
//punem cele doua noduri care formeaza muchia curenta in cate o
//variabila
int nod1 = muchii_ponderate[i][1];
int nod2 = muchii_ponderate[i][2];
//daca nodurile nu fac parte din aceeasi componenta, atunci punem
//muchia in APM, adunam costul muchiei la cel al APM-ului, reunim
//cele doua componente si actualizam numarul de muchii selectate
if (reprez_Kruskal(nod1, tata) != reprez_Kruskal(nod2, tata)){
apm[muchii_selectate].push_back(nod1);
apm[muchii_selectate].push_back(nod2);
cost_apm += muchii_ponderate[i][0];
reunire_Kruskal(nod1, nod2, tata, inaltime);
muchii_selectate++;
//daca am selectat atatea muchii cat ar fi nevoie pentru un
//arbore, atunci APM-ul a fost creat si il returnam
if (muchii_selectate == nr_noduri - 1){
return apm;
}
}
}
return apm;
}
int Graf::reprez_paduri(int nod, vector<int>& tata){
//diferenta fata de functia reprez a algoritmului lui Kruskal este ca
//vom optimiza gasirea reprezentantilor prin procedeul compresiei de cale
//legam toate nodurile de pe lantul din care face parte nodul dat direct
//de radacina (adica egalam tatal lor cu radacina)
if (tata[nod] == 0){
return nod;
}
tata[nod] = reprez_paduri(tata[nod], tata);
return tata[nod];
}
void Graf::reunire_multimi_paduri(int nod1, int nod2, vector<int>& tata, vector<int>& inaltime){
//functie aproape identica cu cea de reunire a algoritmului Kruskal, cu
//exceptia ca vom folosi functia reprez_paduri in loc de reprez_Kruskal
int repr_nod1 = reprez_paduri(nod1, tata);
int repr_nod2 = reprez_paduri(nod2, tata);
if (inaltime[repr_nod1] > inaltime[repr_nod2]){
tata[repr_nod2] = repr_nod1;
} else {
tata[repr_nod1] = repr_nod2;
if (inaltime[repr_nod1] == inaltime[repr_nod2]){
inaltime[repr_nod2]++;
}
}
}
void Graf::paduri_disjuncte(const string fis_in, const string fis_out){
//algoritmul pentru paduri de multimi disjuncte este foarte similar cu
//cel al lui Kruskal pentru APM, cu functia reprez modificata
int nr_op;
ifstream fi(fis_in);
ofstream fo(fis_out);
fi >> nr_noduri >> nr_op;
//declaram un vector de tati si un vector de inaltimi, pentru reuniuni si
//gasiri de reprezentanti eficiente
vector<int> tata(nr_noduri + 1, 0);
vector<int> inaltime(nr_noduri + 1, 0);
for (int i = 0; i < nr_op; i++){
int tip_op;
int nod1, nod2;
fi >> tip_op >> nod1 >> nod2;
//daca operatia ceruta este de tip 1, reunim direct cele doua multimi
//din care fac parte nodurile (nu este nevoie in acest caz sa
//verificam daca nodurile fac parte din multimi diferite)
if (tip_op == 1){
reunire_multimi_paduri(nod1, nod2, tata, inaltime);
} else if (tip_op == 2){
//altfel, daca operatia ceruta este de tip 2, ni se cere sa
//aflam daca cele doua noduri au acelasi reprezentant. Afisam
//corespunzator in functie de raspunsul la aceasta intrebare.
if (reprez_paduri(nod1, tata) == reprez_paduri(nod2, tata)){
fo << "DA\n";
} else {
fo << "NU\n";
}
}
}
fi.close();
fo.close();
}
vector<int> Graf::dijkstra(vector<vector<pair<int, int>>>& muchii_ponderate){
//declaram un vector "distanta" care memoreaza distantele de la nodul 1 la
//celelalte noduri, un vector "tata" care retine tatii nodurilor si un
//heap care va retine perechi de forma (distanta minima, nod) pentru
//selectarea nodurilor in timpul algoritmului
vector<int> distanta(nr_noduri + 1, maxim);
vector<int> tata(nr_noduri + 1, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap_noduri;
//deoarece distanta de la nodul 1 la el insusi este 0, o setam astfel in
//vectorul distanta
distanta[1] = 0;
//initializam heapul, punand elementul primului nod cu distanta 0 si
//restul cu distanta maxim
heap_noduri.push(make_pair(0, 1));
for (int i = 2; i <= nr_noduri; i++){
heap_noduri.push(make_pair(maxim, i));
}
//cat timp avem noduri de prelucrat
while (!heap_noduri.empty()){
//extragem un nod (il scoatem din heap la sfarsit)
int nod = heap_noduri.top().second;
int nr_noduri_adiacente = muchii_ponderate[nod].size();
for (int i = 0; i < nr_noduri_adiacente; i++){
int nod_2 = muchii_ponderate[nod][i].first;
int cost_muchie = muchii_ponderate[nod][i].second;
//daca am gasit o distanta mai mica intre nod_2 si nodul 1 prin
//nod, actualizam distanta si tatal lui nod_2 corespunzator
if (distanta[nod] + cost_muchie < distanta[nod_2]){
distanta[nod_2] = distanta[nod] + cost_muchie;
tata[nod_2] = nod;
}
}
heap_noduri.pop();
}
return distanta;
}
vector<int> Graf::bellman_ford(vector<vector<pair<int, int>>>& muchii_ponderate){
//declaram un vector "distanta" care memoreaza distantele de la nodul 1 la
//celelalte noduri, un vector "tata" care retine tatii nodurilor, un heap
//care va retine perechi de forma (distanta minima, nod) pentru selectarea
//nodurilor in timpul algoritmului si o coada care va retine ordinea in
//care vor fi selectate nodurile la o anumita etapa
vector<int> distanta(nr_noduri + 1, maxim);
vector<int> tata(nr_noduri + 1, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap_noduri;
queue<int> coada_noduri;
//deoarece distanta de la nodul 1 la el insusi este 0, o setam astfel in
//vectorul distanta
distanta[1] = 0;
//deoarece in primul pas trebuie sa alegem toate nodurile, punem in coada
//toate nodurile
for (int i = 1; i <= nr_noduri; i++){
coada_noduri.push(i);
}
//vom avea cel mult nr_noduri - 1 etape (pentru testarea de ciclu negativ)
for (int i = 1; i < nr_noduri; i++){
//scoatem noduri din coada pana cand nu vom mai avea noduri in ea
while (!coada_noduri.empty()){
int nod = coada_noduri.front();
coada_noduri.pop();
int nr_noduri_adiacente = muchii_ponderate[nod].size();
for (int j = 0; j < nr_noduri_adiacente; j++){
int nod_2 = muchii_ponderate[nod][j].first;
int cost_muchie = muchii_ponderate[nod][j].second;
//daca am gasit o distanta mai mica intre nod_2 si nodul 1
//prin nod, actualizam distanta si tatal lui nod_2
//corespunzator si punem in heap nod_2 cu noua lui distanta
if (distanta[nod] + cost_muchie < distanta[nod_2]){
distanta[nod_2] = distanta[nod] + cost_muchie;
tata[nod_2] = nod;
heap_noduri.push(make_pair(distanta[nod_2], nod_2));
}
}
}
//punem noduri in coada in ordinea in care au fost sortate de heap
//(dupa cost) si golim heap-ul treptat pentru adaugarea de noi noduri
//actualizate
while (!heap_noduri.empty()){
coada_noduri.push(heap_noduri.top().second);
heap_noduri.pop();
}
}
return distanta;
}
bool Graf::verif_ciclu_bellman_ford(vector<vector<pair<int, int>>>& muchii_ponderate, vector<int>& distanta, const string fis){
//in acest moment am facut deja n - 1 pasi cu algoritmul principal, deci
//verificam o singura data daca mai exista noduri de actualizat
ofstream fo(fis);
for (int i = 1; i <= nr_noduri; i++){
int nr_noduri_adiacente = muchii_ponderate[i].size();
for (int j = 0; j < nr_noduri_adiacente; j++){
int nod_2 = muchii_ponderate[i][j].first;
int cost_muchie = muchii_ponderate[i][j].second;
//daca am gasit o distanta mai mica intre nod_2 si nodul 1 prin
//nod, deci un nod de actualizat, am gasit un ciclu negativ si
//afisam acest lucru
if (distanta[i] + cost_muchie < distanta[nod_2]){
fo << "Ciclu negativ!";
fo.close();
return true;
}
}
}
fo.close();
return false;
}
int main()
{
Graf g;
//1. algoritmul BFS
/*
int nod_start = g.citire_orientat_bfs("bfs.in");
vector<int> nivel = g.BFS(nod_start);
int numar_noduri = nivel.size();
ofstream fo("bfs.out");
for (int i = 1; i < numar_noduri; i++){
fo << nivel[i] << " ";
}
fo.close();
*/
//2. componente conexe (algoritmul DFS)
/*
g.citire_neorientat("dfs.in");
int nr_comp_conexe = g.componente_conexe();
ofstream fo("dfs.out");
fo << nr_comp_conexe;
fo.close();
*/
//3. componente biconexe
/*
g.citire_neorientat("biconex.in");
//declaram un vector nivel care stocheaza adancimea la care a fost gasit
//un nod (sau -1 daca este nevizitat), un vector low care stocheaza
//nivelul minim la care poate ajunge un anumit nod mergand in fii pe
//drumuri de intoarcere, un vector de vectori comp_biconexe care
//stocheaza componentele biconexe si o stiva de perechi
//muchii_comp_biconexe care stocheaza muchii care vor intra intr-o
//viitoare componenta biconexa
vector<int> nivel;
vector<int> low;
vector<vector<int>> comp_biconexe;
stack<pair<int, int>> muchii_comp_biconexe;
g.componente_biconexe(1, 0, 0, nivel, low, comp_biconexe, muchii_comp_biconexe);
//pornim din
//nodul 1, care va avea adancimea 0
//afisam numarul de componente biconexe
int nr_comp = comp_biconexe.size();
ofstream fo("biconex.out");
fo << nr_comp << "\n";
//incepem sa procesam fiecare componenta pentru afisare
for (int i = 0; i < nr_comp; i++){
//ordonam crescator nodurile care alcatuiesc componenta
sort(comp_biconexe[i].begin(), comp_biconexe[i].end());
//dupa executarea functiei, in comp_biconexe avem muchiile
//componentelor; trebuie sa lasam doar nodurile in componenta
comp_biconexe[i].erase(unique(comp_biconexe[i].begin(), comp_biconexe[i].end()), comp_biconexe[i].end());
//afisam nodurile care alcatuiesc componenta
int n_noduri = comp_biconexe[i].size();
for (int j = 0; j < n_noduri; j++){
fo << comp_biconexe[i][j] << " ";
}
fo << "\n";
}
fo.close();
*/
//4. componente tare conexe (algoritmul lui Tarjan)
/*
g.citire_orientat("ctc.in");
vector<vector<int>> comp_tare_conexe = g.componente_tare_conexe();
int nr_comp = comp_tare_conexe.size();
ofstream fo("ctc.out");
fo << nr_comp << "\n";
//incepem sa procesam fiecare componenta pentru afisare
for (int i = 0; i < nr_comp; i++){
//ordonam crescator nodurile care alcatuiesc componenta
sort(comp_tare_conexe[i].begin(), comp_tare_conexe[i].end());
//afisam nodurile care alcatuiesc componenta
int n_noduri = comp_tare_conexe[i].size();
for (int j = 0; j < n_noduri; j++){
fo << comp_tare_conexe[i][j] << " ";
}
fo << "\n";
}
fo.close();
*/
//5. algoritmul Havel-Hakimi
/*
//declaram un vector secv_grade, care va stoca gradele pe care trebuie
//sa le aiba fiecare nod
vector<int> secv_grade;
int n;
ifstream fi("havelhakimi.in");
fi >> n;
for (int i = 0; i < n; i++){
int grad;
fi >> grad;
secv_grade.push_back(grad);
}
g.havel_hakimi(secv_grade, n, "havelhakimi.out");
fi.close();
*/
//6. sortare topologica
/*
g.citire_orientat("sortaret.in");
vector<int> sortare_top = g.sort_top();
int n = sortare_top.size();
ofstream fo("sortaret.out");
for (int i = 0; i < n; i++){
fo << sortare_top[i] << " ";
}
fo.close();
*/
//7. muchii critice
/*
g.citire_neorientat("critconn.in");
vector<vector<int>> lista_muchii_critice = g.muchii_critice();
int nr_muchii_critice = lista_muchii_critice.size();
ofstream fo("critconn.out");
for (int i = 0; i < nr_muchii_critice; i++){
//afisam muchiile critice, vectori de exact 2 elemente (cele 2 noduri)
for (int j = 0; j < 2; j++){
fo << lista_muchii_critice[i][j] << " ";
}
fo << "\n";
}
fo.close();
*/
//8. arbore partial de cost minim (APM) - algoritmul lui Kruskal
/*
//declaram un vector de vectori "m_cost" in care vom pune muchiile cu
//costurile asociate si o variabila "cost_apm" in care vom stoca costul
//cerut al APM-ului
vector<vector<int>> m_cost = g.citire_neorientat_cost("apm.in");
int cost_apm = 0;
//declaram un vector de vectori "apm" in care stocam muchiile APM-ului
//cerut
vector<vector<int>> apm = g.apm_Kruskal(m_cost, cost_apm);
int nr_muchii_apm = apm.size();
ofstream fo("apm.out");
fo << cost_apm << "\n";
fo << nr_muchii_apm << "\n";
for (int i = 0; i < nr_muchii_apm; i++){
//fiecare muchie este stocata intr-un vector cu exact 2 elemente
fo << apm[i][0] << " " << apm[i][1] << "\n";
}
fo.close();
*/
//9. paduri de multimi disjuncte
//g.paduri_disjuncte("disjoint.in", "disjoint.out");
//10. algoritmul lui Dijkstra
vector<vector<pair<int, int>>> muchii_ponderate = g.citire_orientat_cost("dijkstra.in");
vector<int> lista_distante = g.dijkstra(muchii_ponderate);
int nr_distante = lista_distante.size();
ofstream fo("dijkstra.out");
for (int i = 2; i < nr_distante; i++){
fo << lista_distante[i] << " ";
}
fo.close();
//11. algoritmul Bellman-Ford
/*
vector<vector<pair<int, int>>> muchii_ponderate = g.citire_orientat_cost("bellmanford.in");
vector<int> lista_distante = g.bellman_ford(muchii_ponderate);
ofstream fo("bellmanford.out");
//daca NU avem niciun ciclu negativ in graf, afisam distantele cerute
if (!g.verif_ciclu_bellman_ford(muchii_ponderate, lista_distante, "bellmanford.out")){
int nr_distante = lista_distante.size();
for (int i = 2; i < nr_distante; i++){
fo << lista_distante[i] << " ";
}
}
fo.close();
*/
return 0;
}
Ioana Velniceru ioana2008v