#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_set>
#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
bool BFS_construire_lant(vector<int>& tata, vector<vector<pair<int, int>>>& muchii_ponderate, vector<vector<pair<int, int>>>& fluxuri, vector<unordered_set<int>>& lista_arce);
//functie apelata din edmonds_karp care construieste un lant pe unde
//putem sa adaugam flux
int revizuire_flux(vector<int>& tata, vector<vector<pair<int, int>>>& muchii_ponderate, vector<vector<pair<int, int>>>& fluxuri);
//functie apelata din edmonds_karp care modifica fluxul pe lantul obtinut cu
//ajutorul functiei BFS_construire_lant
vector<int> gasire_ciclu_euler(vector<pair<int, int>>& lista_muchii);
//functie apelata din ciclu_euler care gaseste si returneaza ciclul
//eulerian al unui graf care indeplineste conditia sa aiba acest ciclu
bool BFS_cuplaj_maxim(vector<int>& pereche_L, vector<int>& pereche_R, vector<int>& nivel);
//functie apelata din cuplaj_maxim_hopcroft_karp care face un BFS pe
//graful bipartit cu rolul de a gasi noduri din multimea R necuplate cu
//noduri din multimea L care au muchie spre ele
bool DFS_cuplaj_maxim(int nod_L, vector<int>& pereche_L, vector<int>& pereche_R, vector<int>& nivel);
//functie apelata din cuplaj_maxim_hopcroft_karp care face un DFS pe
//graful bipartit cu rolul de a modifica sau adauga un cuplaj pentru un
//nod dat din multimea L
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<vector<pair<int, int>>> citire_retea(vector<unordered_set<int>>& lista_arce, const string fis);
//functie de citire specifica problemei
//Edmonds-Karp (maxflow); identica cu
//citire_orientat_cost, cu exceptia ca vom
//pune arcele si intr-un vector de hash-uri
//pentru a putea gasi arcele inverse in
//timpul algoritmului Edmonds-Karp
vector<vector<int>> citire_orientat_cost_matrice(const string fis);
//functie de citire specifica problemei
//Floyd-Warshall (royfloyd); citeste matricea
//de distante data
vector<pair<int, int>> citire_neorientat_muchii(const string fis);
//functie de citire specifica algoritmului de
//gasire a ciclului eulerian; identica cu
//citire_neorientat, cu exceptia ca vom retine
//si vectorul de muchii pentru a le prelucra
vector<vector<int>> citire_orientat_cost_hamilton(const string fis);
//functie de citire specifica algoritmului de
//gasire a ciclului hamiltonian; asemanator cu
//citire_orientat_cost, dar retinem costurile
//muchiilor separat si lista adiacenta
//"invers" pentru a cauta nodurile care au
//muchie spre un nod dat in algoritmul
//principal
void citire_arbore(const string fis);
//functie de citire specifica problemei
//diametrului arborelui (darb); identica cu
//citire_neorientat, cu exceptia faptului ca
//vom citi doar numarul de noduri (numarul
//de muchii este implicit nr_noduri - 1)
int citire_bipartit(const string fis);
//functie de citire specifica problemei
//Hopcroft-Karp (cuplaj maxim); identica cu
//citire_orientat, cu exceptia ca vom citi si
//numarul de noduri al multimii R
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, bool& exista_ciclu, const string fis);
//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. Functia testeaza si daca exista un ciclu negativ in
//graf.
int edmonds_karp(vector<vector<pair<int, int>>>& muchii_ponderate, vector<unordered_set<int>>& lista_arce);
//functie care ia un vector de muchii cu costuri pentru fiecare nod si un
//vector de hash-uri care retine lista de muchii pentru fiecare nod. Ea
//returneaza fluxul maxim care se poate trimite pe reteaua data.
vector<vector<int>> floyd_warshall(vector<vector<int>> muchii_ponderate);
//functie care ia o matrice de distante pentru fiecare muchie. Ea
//returneaza o matrice de distante minime intre fiecare nod al grafului.
void BFS_diametru_arbore(int nod_start, int& ultim, int& diametru);
//functie care face algoritmul de BFS pe un graf pornind de la nodul de
//start, retinand la sfarsit ultimul nod parcurs si nivelul la care se
//afla acesta (care va fi diametrul arborelui dupa a doua apelare)
void ciclu_euler(vector<pair<int, int>>& lista_muchii, vector<int>& ciclu_eulerian, const string fis);
//functie care verifica pentru un multigraf daca poate avea un ciclu
//eulerian si, daca da, apeleaza o functie care il gaseste
int ciclu_hamilton(vector<vector<int>>& costuri_muchii);
//functie care ia un graf orientat cu costuri si care verifica daca acesta
//are cel putin un ciclu hamiltonian; daca da, returneaza costul minim al
//unui astfel de ciclu
int cuplaj_maxim_hopcroft_karp(int nr_noduri_R, vector<pair<int, int>>& cuplaje);
//functie care ia un graf bipartit si care returneaza cuplajul maxim al
//acestui graf
};
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<vector<pair<int, int>>> Graf::citire_retea(vector<unordered_set<int>>& lista_arce, 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; de asemenea, vom pune muchiile intr-un vector de hash-uri
//pentru a gasi arcele inverse ale unui nod
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>());
muchii_ponderate.push_back(vector<pair<int, int>>());
lista_arce.push_back(unordered_set<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));
lista_arce[nod_1].insert(nod_2);
}
fi.close();
return muchii_ponderate;
}
vector<vector<int>> Graf::citire_orientat_cost_matrice(const string fis){
vector<vector<int>> muchii_ponderate;
ifstream fi(fis);
fi >> nr_noduri;
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<int>());
}
for (int i = 0; i < nr_noduri; i++){
for (int j = 0; j < nr_noduri; j++){
int dist;
fi >> dist;
if (dist){
lista_adiacenta[i].push_back(j);
}
muchii_ponderate[i].push_back(dist);
}
}
fi.close();
return muchii_ponderate;
}
void Graf::citire_arbore(const string fis){
ifstream fi(fis);
fi >> nr_noduri;
nr_muchii = nr_noduri - 1;
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();
}
vector<pair<int, int>> Graf::citire_neorientat_muchii(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>());
}
vector<pair<int, int>> lista_muchii;
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);
lista_muchii.push_back(make_pair(nod_1, nod_2));
}
fi.close();
return lista_muchii;
}
vector<vector<int>> Graf::citire_orientat_cost_hamilton(const string fis){
//vom retine costurile muchiilor separat, din cauza retinerii diferite a
//listei de adiacenta
vector<vector<int>> costuri_muchii;
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++){
costuri_muchii.push_back(vector<int>());
for (int j = 1; j <= nr_noduri + 1; j++){
costuri_muchii[i - 1].push_back(maxim);
}
}
for (int i = 0; i < nr_muchii; i++){
int nod_1, nod_2, cost;
fi >> nod_1 >> nod_2 >> cost;
//diferenta fata de citire_orientat_cost este ca in lista de adiacenta
//se vor pune arcele "inverse", deoarece algoritmul va folosi lista
//pentru a cauta, dat fiind un nod, nodurile care au arc spre el.
lista_adiacenta[nod_2].push_back(nod_1);
costuri_muchii[nod_1][nod_2] = cost;
}
fi.close();
return costuri_muchii;
}
int Graf::citire_bipartit(const string fis){
ifstream fi(fis);
//vom citi si numarul de noduri din multimea R, pe care il vom returna
int nr_noduri_2;
fi >> nr_noduri >> nr_noduri_2 >> 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();
return nr_noduri_2;
}
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; 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 "vizitat" care retine ce noduri sunt
//vizitate 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<bool> vizitat(nr_noduri + 1, false);
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
heap_noduri.push(make_pair(0, 1));
//cat timp avem noduri de prelucrat
while (!heap_noduri.empty()){
//extragem un nod
int nod = heap_noduri.top().second;
heap_noduri.pop();
//marcam nodul extras drept vizitat
vizitat[nod] = true;
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 de la nodul 1 la nod_2 prin
//nod, iar nod_2 nu a mai fost vizitat, actualizam distanta si
//tatal lui nod_2 corespunzator si punem nod_2 in heap pentru a
//fi prelucrat
if ((!vizitat[nod_2]) && (distanta[nod] + cost_muchie < distanta[nod_2])){
distanta[nod_2] = distanta[nod] + cost_muchie;
heap_noduri.push(make_pair(distanta[nod_2], nod_2));
}
}
}
return distanta;
}
vector<int> Graf::bellman_ford(vector<vector<pair<int, int>>>& muchii_ponderate, bool& exista_ciclu, const string fis){
//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);
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;
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::BFS_construire_lant(vector<int>& tata, vector<vector<pair<int, int>>>& muchii_ponderate, vector<vector<pair<int, int>>>& fluxuri, vector<unordered_set<int>>& lista_arce){
//resetam vectorul tata pentru a incepe un nou BFS
for (int i = 1; i <= nr_noduri; i++){
tata[i] = 0;
}
vector<bool> vizitat(nr_noduri + 1, false);
queue<int> coada_noduri;
coada_noduri.push(1);
while (!coada_noduri.empty()){
int nod = coada_noduri.front();
//cautam arcele directe, lucrand direct pe vectorul de muchii
int nr_noduri_adiacente = muchii_ponderate[nod].size();
for (int i = 0; i < nr_noduri_adiacente; i++){
//preluam un nod adiacent
int nod_2 = muchii_ponderate[nod][i].first;
//daca nu am mai vizitat nodul gasit si mai putem trimite flux pe
//muchia dintre nod initial si cel adiacent, punem nodul gasit in
//coada
if ((!vizitat[nod_2]) && (muchii_ponderate[nod][i].second > fluxuri[nod][i].second)){
coada_noduri.push(nod_2);
vizitat[nod_2] = true;
tata[nod_2] = nod;
//daca am ajuns la nodul destinatie, am construit lantul cerut
if (nod_2 == nr_noduri){
return true;
}
}
}
//cautam arcele inverse, cautand posibile muchii intre toate nodurile
//si nodul luat din coada
for (int i = 1; i <= nr_noduri; i++){
//daca am gasit muchia dintre nodul i si nodul din coada in
//vectorul de hash-uri, putem sa o cautam si in vectorul de
//muchii
if ((i != nod) && (lista_arce[i].find(nod) != lista_arce[i].end())){
int j = 0;
while (muchii_ponderate[i][j].first != nod){
j++;
}
//daca putem scoate flux din muchie, adaugam nodul i in coada
//si setam tatal ca fiind -(nod) pentru a marca faptul ca
//avem un arc invers intre cele doua noduri
if ((!vizitat[i]) && (fluxuri[i][j].second > 0)){
coada_noduri.push(i);
vizitat[i] = true;
tata[i] = (-1) * (nod);
//daca nodul i este cel destinatie, am construit lantul
//cerut
if (i == nr_noduri){
return true;
}
}
}
}
coada_noduri.pop();
}
return false;
}
int Graf::revizuire_flux(vector<int>& tata, vector<vector<pair<int, int>>>& muchii_ponderate, vector<vector<pair<int, int>>>& fluxuri){
//initial, fluxul cu care revizuim lantul va fi un numar INF (maxim)
int flux_adaugat = maxim;
//calculam fluxul, reconstituind drumul invers, de la destinatie la sursa
for (int nod = nr_noduri; nod != 1; nod = tata[nod]){
int i = 0;
int nod_2 = tata[nod];
while (muchii_ponderate[nod_2][i].first != nod){
i++;
}
//fluxul va fi minimul dintre fluxul gasit pana in acest moment si
//fluxul care se mai poate adauga pe muchia curenta
flux_adaugat = min(flux_adaugat, muchii_ponderate[nod_2][i].second - fluxuri[nod_2][i].second);
}
//modificam fluxul pe lant
for (int nod = nr_noduri; nod != 1; nod = tata[nod]){
int i = 0;
int nod_2 = tata[nod];
//daca arcul este direct, adaugam fluxul gasit anterior la fluxul
//arcului
if (nod_2 > 0){
while (muchii_ponderate[nod_2][i].first != nod){
i++;
}
fluxuri[nod_2][i].second += flux_adaugat;
} else {
//pentru arce inverse, scadem fluxul gasit anterior la fluxul
//arcului
nod_2 *= -1;
while (muchii_ponderate[nod][i].first != nod_2){
i++;
}
fluxuri[nod][i].second -= flux_adaugat;
}
}
return flux_adaugat;
}
int Graf::edmonds_karp(vector<vector<pair<int, int>>>& muchii_ponderate, vector<unordered_set<int>>& lista_arce){
vector<vector<pair<int, int>>> fluxuri;
vector<int> tata(nr_noduri + 1, 0);
for (int i = 1; i <= nr_noduri + 1; i++){
fluxuri.push_back(vector<pair<int, int>>());
}
//initial, vom avea fluxul 0 pe toate arcele
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++){
fluxuri[i].push_back(make_pair(muchii_ponderate[i][j].first, 0));
}
}
//fluxul cerut va fi initial 0
int flux_total = 0;
//cat timp putem construi lanturi pe care putem adauga flux, modificam
//fluxul pe aceste lanturi
while (BFS_construire_lant(tata, muchii_ponderate, fluxuri, lista_arce)){
int flux = revizuire_flux(tata, muchii_ponderate, fluxuri);
//adaugam fluxul gasit pe fiecare lant la fluxul total cerut
flux_total += flux;
}
return flux_total;
}
vector<vector<int>> Graf::floyd_warshall(vector<vector<int>> muchii_ponderate){
vector<vector<int>> distante_minime;
for (int i = 1; i <= nr_noduri; i++){
distante_minime.push_back(vector<int>());
}
for (int i = 0; i < nr_noduri; i++){
for (int j = 0; j < nr_noduri; j++){
//initial, distantele minime vor fi cele directe de la nodul i la
//nodul j
distante_minime[i].push_back(muchii_ponderate[i][j]);
}
}
//cautam distante minime de la toate nodurile i la toate nodurile j prin
//nodul k
for (int k = 0; k < nr_noduri; k++){
for (int i = 0; i < nr_noduri; i++){
for (int j = 0; j < nr_noduri; j++){
//daca gasim o distanta mai mica decat cea curenta prin nodul
//k, atunci actualizam distanta curenta
if (distante_minime[i][j] > distante_minime[i][k] + distante_minime[k][j]){
distante_minime[i][j] = distante_minime[i][k] + distante_minime[k][j];
}
}
}
}
return distante_minime;
}
void Graf::BFS_diametru_arbore(int nod_start, int& ultim, int& diametru){
//algoritmul este identic cu cel de BFS, cu exceptia faptului ca utilizam
//o variabila care stocheaza ultimul nod parcurs, "ultim", si o variabila
//care stocheaza diametrul cerut dupa doua apelari ale acestei functii,
//"diametru"
vector<bool> vizitat(nr_noduri + 1, false);
queue<int> coada_varfuri;
vector<int> nivel(nr_noduri + 1, nul);
coada_varfuri.push(nod_start);
vizitat[nod_start] = true;
nivel[nod_start] = 1;
while (!coada_varfuri.empty()){
int nod = coada_varfuri.front();
for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
if (!vizitat[*i]){
coada_varfuri.push(*i);
vizitat[*i] = true;
nivel[*i] = nivel[nod] + 1;
//actualizam ultimul nod gasit si diametrul dupa fiecare nou
//nod nevizitat gasit; diametrul va fi nivelul nodului gasit
//(care, in final, va fi nivelul ultimului nod gasit in BFS-ul
//care porneste din ultimul nod gasit in primul apel)
ultim = *i;
diametru = nivel[*i];
}
}
coada_varfuri.pop();
}
}
vector<int> Graf::gasire_ciclu_euler(vector<pair<int, int>>& lista_muchii){
//declaram o stiva de noduri pentru procesarea nodurilor si un vector
//"vizitat" care stocheaza care muchii au fost vizitate
vector<int> ciclu;
stack<int> stiva_noduri;
vector<bool> vizitat(nr_muchii + 1, false);
//la inceput, punem nodul 1 in stiva
stiva_noduri.push(1);
//scoatem noduri din stiva cat timp avem noduri de procesat
while (!stiva_noduri.empty()){
int nod = stiva_noduri.top();
int muchie = 0;
bool gasit_muchie = false;
//cautam o muchie adiacenta si nevizitata pentru nodul dat
while (muchie < nr_muchii && !gasit_muchie){
//daca am gasit o astfel de muchie, marcam acest fapt, altfel
//continuam cautarea
if (((lista_muchii[muchie].first == nod) || (lista_muchii[muchie].second == nod)) && !vizitat[muchie]){
gasit_muchie = true;
} else {
muchie++;
}
}
//daca am gasit muchia data, o marcam drept vizitata
if (gasit_muchie){
vizitat[muchie] = true;
int nod_2;
//punem celalalt nod al muchiei in stiva pentru procesare
if (nod == lista_muchii[muchie].first){
nod_2 = lista_muchii[muchie].second;
} else {
nod_2 = lista_muchii[muchie].first;
}
stiva_noduri.push(nod_2);
} else {
//daca nu mai gasim astfel de muchii, s-a terminat procesarea
//nodului, deci il scoatem din stiva si il punem in ciclul cerut
stiva_noduri.pop();
ciclu.push_back(nod);
}
}
return ciclu;
}
void Graf::ciclu_euler(vector<pair<int, int>>& lista_muchii, vector<int>& ciclu_eulerian, const string fis){
//verificam conditia de ciclu eulerian (daca toate nodurile au grad par)
for (int nod = 1; nod <= nr_noduri; nod++){
int grad_nod = lista_adiacenta[nod].size();
//daca un nod are grad impar, afisam ca nu are solutie si ne oprim
if (grad_nod % 2 != 0){
ofstream fo(fis);
fo << "-1";
fo.close();
return;
}
}
//altfel, incepem algoritmul de gasire a ciclului
ciclu_eulerian = gasire_ciclu_euler(lista_muchii);
}
int Graf::ciclu_hamilton(vector<vector<int>>& costuri_muchii){
//declaram o matrice care va memora costul minim al unui nod dat, data
//fiind o ruta compusa din anumite noduri.
//ruta va fi exprimata printr-un numar de la 0 pana la 2^nr_noduri - 1,
//care, in scrierea sa in baza 2, marcheaza ce noduri fac parte din ruta.
//de exemplu, 5 este configuratia rutei compusa din nodurile 0 si 2,
//deoarece 5 = (101)2 = 2^0 + 2^2.
vector<vector<int>> cost_cu_ruta_nod;
for (int i = 0; i < 1 << nr_noduri; i++){
cost_cu_ruta_nod.push_back(vector<int>(nr_noduri, maxim));
}
//initializam costul minim pana la nodul 0 pe ruta cu nodul 0 ca fiind 0.
cost_cu_ruta_nod[1][0] = 0;
//parcurgem toate rutele posibile si incercam sa calculam costul minim
//pentru fiecare nod prin aceste rute
for (int ruta = 0; ruta < 1 << nr_noduri; ruta++){
for (int nod = 0; nod < nr_noduri; nod++){
//procesam toate nodurile care fac parte din ruta curenta
//daca un nod apartine unei rute, si-ul pe biti dintre numarul
//rutei si 2^nod va fi nenul
if (ruta & (1 << nod)){
//procesam toate nodurile care au muchie spre nodul gasit
//(tinem lista de adiacenta "invers" cu acest scop inca de la
//citire); le vom numi "noduri adiacente" in explicatiile ce
//urmeaza
int nr_muchii_adiacente = lista_adiacenta[nod].size();
for (int i = 0; i < nr_muchii_adiacente; i++){
//daca un nod adiacent exista in ruta, putem actualiza
//costul minim al nodului "nod" pe aceasta ruta
if (ruta & (1 << lista_adiacenta[nod][i])){
//actualizam costul minim, care va fi minimul dintre
//costul gasit pana in acest punct si suma dintre
//costul minim pana la nodul adiacent cu
//ruta care exclude nodul "nod" si costul muchiei
//dintre nodul adiacent si nodul initial gasit;
//stergerea nodului din ruta se va face cu ajutorul
//xor-ului pe biti, mai precis: ruta xor (2^nod).
cost_cu_ruta_nod[ruta][nod] = min(cost_cu_ruta_nod[ruta][nod], cost_cu_ruta_nod[ruta ^ (1 << nod)][lista_adiacenta[nod][i]] + costuri_muchii[lista_adiacenta[nod][i]][nod]);
}
}
}
}
}
int cost_minim = maxim;
//costul minim cerut va fi cea mai mica valoare a sumei dintre costul
//minim pana la un nod adiacent cu nodul 0 pe ruta compusa din toate
//nodurile grafului si costul muchiei dintre nodul adiacent si nodul 0
int n_muchii_ad = lista_adiacenta[0].size();
for (int i = 0; i < n_muchii_ad; i++){
cost_minim = min(cost_minim, cost_cu_ruta_nod[(1 << nr_noduri) - 1][lista_adiacenta[0][i]] + costuri_muchii[lista_adiacenta[0][i]][0]);
}
return cost_minim;
}
bool Graf::BFS_cuplaj_maxim(vector<int>& pereche_L, vector<int>& pereche_R, vector<int>& nivel){
//declaram o coada de noduri in care vom pune nodurile de procesat
queue<int> coada_noduri;
for (int l = 1; l <= nr_noduri; l++){
//la inceput, vom pune in coada nodurile din multimea L necuplate
//daca un nod din L este necuplat, ii schimbam de asemenea nivelul
//pentru a-l marca in curs de procesare
if (pereche_L[l] == 0){
nivel[l] = 0;
coada_noduri.push(l);
} else {
//altfel, nu procesam nodul (momentan; inca este posibil sa fie
//procesat)
nivel[l] = maxim;
}
}
//initializam nivelul unui nod "nul" ca fiind maxim
nivel[0] = maxim;
//cat timp avem noduri de procesat
while (!coada_noduri.empty()){
int nod_L = coada_noduri.front();
coada_noduri.pop();
//daca nodul trebuie procesat
if (nivel[nod_L] < nivel[0]){
//parcurgem toate nodurile din R care sunt adiacente cu el
int nr_muchii_adiacente = lista_adiacenta[nod_L].size();
for (int i = 0; i < nr_muchii_adiacente; i++){
int nod_R = lista_adiacenta[nod_L][i];
//daca gasim un nod cu nivelul neinitializat (de obicei un nod
//deja cuplat sau cel nul), il procesam: ii actualizam nivelul
//cu cel al nodului + 1 si il punem in coada
//daca am gasit nodul nul, nu se vor mai adauga noduri in
//coada pentru ca nivelul nu poate creste peste cel al
//nodului nul
if (nivel[pereche_R[nod_R]] == maxim){
nivel[pereche_R[nod_R]] = nivel[nod_L] + 1;
coada_noduri.push(pereche_R[nod_R]);
}
}
}
}
//daca am gasit nodul nul (adica daca am dat de noduri din R necuplate),
//returnam true, altfel false si deci algoritmul se termina
return nivel[0] != maxim;
}
bool Graf::DFS_cuplaj_maxim(int nod_L, vector<int>& pereche_L, vector<int>& pereche_R, vector<int>& nivel){
//daca nodul nu este cel nul, putem face DFS cu el, altfel returnam true
if (nod_L != 0){
//parcurgem nodurile din R adiacente cu nodul dat
int nr_muchii_adiacente = lista_adiacenta[nod_L].size();
for (int i = 0; i < nr_muchii_adiacente; i++){
int nod_R = lista_adiacenta[nod_L][i];
//daca am marcat nodul din L care este acum cuplat cu nodul din R
//ca fiind urmatorul de procesat, continuam DFS-ul
if (nivel[pereche_R[nod_R]] == nivel[nod_L] + 1){
//daca, terminand algoritmul de DFS, ajungem la nodul nul,
//actualizam cuplajele nodurilor pe care le-am intalnit pe
//parcursul algoritmului de DFS si returnam true
if (DFS_cuplaj_maxim(pereche_R[nod_R], pereche_L, pereche_R, nivel)){
pereche_R[nod_R] = nod_L;
pereche_L[nod_L] = nod_R;
return true;
}
}
}
//altfel, marcam ca nu am gasit niciun cuplaj pentru nod si returnam
//false
nivel[nod_L] = maxim;
return false;
}
return true;
}
int Graf::cuplaj_maxim_hopcroft_karp(int nr_noduri_R, vector<pair<int, int>>& cuplaje){
//declaram vectorii pereche_L si pereche_R care vor indica pentru fiecare
//nod din fiecare multime care este nodul cu care sunt cuplati, si un
//vector nivel folosit pentru DFS-ul algoritmului si pentru a marca
//diferite stari ale nodurilor din multimea L
vector<int> pereche_L(nr_noduri + 1, 0);
vector<int> pereche_R(nr_noduri_R + 1, 0);
vector<int> nivel(nr_noduri + 1, 0);
int cuplaj_maxim = 0;
//cautam cu ajutorul unui BFS noduri din multimes R necuplate care pot fi
//cuplate cu un nod din multimea L
while (BFS_cuplaj_maxim(pereche_L, pereche_R, nivel)){
for (int l = 1; l <= nr_noduri; l++){
//pentru nodurile necuplate din multimea L, incercam sa le gasim
//un cuplaj printr-un DFS
if (pereche_L[l] == 0){
if (DFS_cuplaj_maxim(l, pereche_L, pereche_R, nivel)){
//daca am gasit un astfel de cuplaj, incrementam numarul
//de cuplaje gasite
cuplaj_maxim++;
}
}
}
}
for (int l = 1; l <= nr_noduri; l++){
if (pereche_L[l] != 0){
cuplaje.push_back(make_pair(l, pereche_L[l]));
}
}
return cuplaj_maxim;
}
void BFS_helper(){
Graf g;
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();
}
void DFS_helper(){
Graf g;
g.citire_neorientat("dfs.in");
int nr_comp_conexe = g.componente_conexe();
ofstream fo("dfs.out");
fo << nr_comp_conexe;
fo.close();
}
void biconex_helper(){
Graf g;
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();
}
void CTC_helper(){
Graf g;
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();
}
void havel_hakimi_helper(){
Graf g;
//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();
}
void sort_top_helper(){
Graf g;
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();
}
void critical_connections_helper(){
Graf g;
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();
}
void APM_helper(){
Graf g;
//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();
}
void paduri_disjuncte_helper(){
Graf g;
g.paduri_disjuncte("disjoint.in", "disjoint.out");
}
void dijkstra_helper(){
Graf g;
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();
}
void bellmanford_helper(){
Graf g;
vector<vector<pair<int, int>>> muchii_ponderate = g.citire_orientat_cost("bellmanford.in");
bool exista_ciclu = false;
vector<int> lista_distante = g.bellman_ford(muchii_ponderate, exista_ciclu, "bellmanford.out");
ofstream fo("bellmanford.out");
//daca NU avem niciun ciclu negativ in graf, afisam distantele cerute
if (!exista_ciclu){
int nr_distante = lista_distante.size();
for (int i = 2; i < nr_distante; i++){
fo << lista_distante[i] << " ";
}
}
fo.close();
}
void edmonds_karp_helper(){
Graf g;
vector<unordered_set<int>> lista_arce;
vector<vector<pair<int, int>>> muchii_ponderate = g.citire_retea(lista_arce, "maxflow.in");
int flux_maxim = g.edmonds_karp(muchii_ponderate, lista_arce);
ofstream fo("maxflow.out");
fo << flux_maxim;
fo.close();
}
void floyd_warshall_helper(){
Graf g;
vector<vector<int>> muchii_ponderate = g.citire_orientat_cost_matrice("royfloyd.in");
vector<vector<int>> distante_minime = g.floyd_warshall(muchii_ponderate);
ofstream fo("royfloyd.out");
int numar_noduri = distante_minime.size();
for (int i = 0; i < numar_noduri; i++){
for (int j = 0; j < numar_noduri; j++){
fo << distante_minime[i][j] << " ";
}
fo << "\n";
}
fo.close();
}
void diametru_arbore_helper(){
Graf g;
g.citire_arbore("darb.in");
int ultim = 0;
int diametru = 0;
//primul apel al BFS-ului va fi din nodul 1
g.BFS_diametru_arbore(1, ultim, diametru);
//al doilea apel al BFS-ului este din ultimul nod gasit in primul apel si
//va da diametrul cerut
g.BFS_diametru_arbore(ultim, ultim, diametru);
ofstream fo("darb.out");
fo << diametru;
fo.close();
}
void ciclu_eulerian_helper(){
Graf g;
vector<pair<int, int>> lista_muchii = g.citire_neorientat_muchii("ciclueuler.in");
vector<int> ciclu_eulerian;
g.ciclu_euler(lista_muchii, ciclu_eulerian, "ciclueuler.out");
//daca vectorul cu ciclul dat este gol, inseamna ca nu l-am gasit (ca
//ne-am oprit la verificarea conditiei de ciclu); altfel, afisam ciclul
if (!ciclu_eulerian.empty()){
ofstream fo("ciclueuler.out");
int lungime_ciclu = ciclu_eulerian.size();
for (int i = 0; i < lungime_ciclu - 1; i++){
fo << ciclu_eulerian[i] << " ";
}
fo.close();
}
}
void ciclu_hamiltonian_helper(){
Graf g;
vector<vector<int>> costuri_muchii = g.citire_orientat_cost_hamilton("hamilton.in");
int cost_minim = g.ciclu_hamilton(costuri_muchii);
ofstream fo("hamilton.out");
//daca costul minim este egal cu valoarea maxima a unui cost, inseamna ca
//valoarea lui initiala nu s-a modificat, deci ca nu am gasit ciclul
//hamiltonian cerut; Altfel, afisam costul minim asociat cu acesta
if (cost_minim == maxim){
fo << "Nu exista solutie";
} else {
fo << cost_minim;
}
fo.close();
}
void cuplaj_maxim_helper(){
Graf g;
int nr_noduri_R = g.citire_bipartit("cuplaj.in");
vector<pair<int, int>> cuplaje;
int cuplaj_maxim = g.cuplaj_maxim_hopcroft_karp(nr_noduri_R, cuplaje);
ofstream fo("cuplaj.out");
fo << cuplaj_maxim << "\n";
int nr_cuplaje = cuplaje.size();
for (int i = 0; i < nr_cuplaje; i++){
fo << cuplaje[i].first << " " << cuplaje[i].second << "\n";
}
fo.close();
}
int main()
{
//1. algoritmul BFS
//BFS_helper();
//2. componente conexe (algoritmul DFS)
//DFS_helper();
//3. componente biconexe
//biconex_helper();
//4. componente tare conexe (algoritmul lui Tarjan)
//CTC_helper();
//5. algoritmul Havel-Hakimi
//havel_hakimi_helper();
//6. sortare topologica
//sort_top_helper();
//7. muchii critice
//critical_connections_helper();
//8. arbore partial de cost minim (APM) - algoritmul lui Kruskal
//APM_helper();
//9. paduri de multimi disjuncte
//paduri_disjuncte_helper();
//10. algoritmul lui Dijkstra
//dijkstra_helper();
//11. algoritmul Bellman-Ford
//bellmanford_helper();
//12. flux maxim (algoritmul Edmonds-Karp)
//edmonds_karp_helper();
//13. algoritmul Floyd-Warshall
floyd_warshall_helper();
//14. diametrul unui arbore
//diametru_arbore_helper();
//15. ciclu eulerian
//ciclu_eulerian_helper();
//16. ciclu hamiltonian
//ciclu_hamiltonian_helper();
//17. cuplaj maxim (algoritmul Hopcroft-Karp)
//cuplaj_maxim_helper();
return 0;
}
Ioana Velniceru ioana2008v