//#ifndef AF_LABORATOR1_GRAF_H
//#define AF_LABORATOR1_GRAF_H
//
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <queue>
//#include <algorithm>
//#include <cassert>
//#include <stack>
//#include <set>
//#include<cstdio>
//
//using namespace std;
//
//ifstream fin("ciclueuler.in");
//ofstream fout("ciclueuler.out");
//
////strucutra unui arc cu distanta(cost) din graf(folosita in metodele Dijkstra si Bellman_Ford si de clasa Min_heap)
//struct arc
//{
// int y, distanta;
// arc(int b, int d)
// {
// y = b;
// distanta = d;
// }
// arc(){}
// bool operator < (const arc &a) const //operator pentru compararea distantelor(costurilor) a doua arce
// {return distanta < a.distanta;}
//};
//
//
//class Graf
//{
//private:
// //strucutra unei muchii din graf(folosita in medota Biconexe)
// struct muchie
// {
// int x,y;
// muchie(int a, int b)
// {
// x=a;
// y=b;
// }
// muchie(){}
// };
// //strucutra unei muchii cu cost din graf(folosita in medota Kruskal)
// struct muchie_cost
// {
// int x,y,cost;
// muchie_cost(int a, int b, int c)
// {
// x=a;
// y=b;
// cost=c;
// }
// muchie_cost(){}
// bool operator < (const muchie_cost &m) const //operator pentru compararea costurilor a doua muchii
// {return cost < m.cost;}
// };
//
//
// int n; //nr de noduri
// int m; //nr de muchii
// vector<int> rezultat;//vectorul in care se va construi rezultatul functiilor recursive
// vector<int> tati;//vectorul de tati folosit in parcurgeri(vector utilizat in comun de metodele bfs_maxflow si Maxflow)
// vector<bool> vizitat; //vector folosita in parcurgeri pentru a retine ce noduri au fot vizitate
// vector<vector<int>> flux; //matrice in care se moreaza fluxurile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
// vector<vector<int>> capacitate; //matrice in care se moreaza capacitatile dintre doua noduri adiacente din graf(utilizat in comun de metodele bfs_maxflow si Maxflow)
// vector<vector<int>> la; //vector cu listele de adiacenta
// vector<muchie_cost> vmc; //vector de muchii cu cost
// vector<vector<arc>> la_arce; //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
// bool orientat; //variabila care ne spune daca graful este orientat sau nu(daca este orientat este true altfel este false)
// bool costuri;//variabila care ne spune daca muchiile grafului au sau nu asociate costuri(daca da costuri este true altfel este false)
// void dfs_rec(int x, vector<int> & parcurgere, vector<int> & vizitat); //dfs = parcurgere dfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
// void dfs_mc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat);//subprogram de tip dfs folosit de metoda Muchii_critice
// void dfs_bcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat); //subprogram de tip dfs folosit de metoda Biconexe
// void dfs_ctc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat);//subprogram de tip dfs folosit de metoda Componente_Tare_Conexe
// bool bfs_maxflow(int S, int D);//metoda ce implementeaza o parcurgere bfs si intoarce false daca din sursa nu se poate ajunge in destinatie, folosita in algoritmul Edmonds-Karp;
// //complexitate O(n)
//
//public:
// Graf(int n, int m, bool orientat, bool costuri);//constructor parametrizat care primeste si tipul grafului si daca muchiile au sau nu costuri: orientat(tip==true) sau neorientat(tip==false) si cu costuri pe muchii(costuri==true) sau fara(costuri==false)
// void Add_edge(int x, int y); //metoda de adaugare a unei muchii in graf
// void Add_edge_c(int x, int y, int c); //metoda de adaugare a unei muchii cu cost in graf
// void Add_arc(int x, int y, int d); //metoda de adaugare a unui arc cu distanta in graf
// vector<int> dfs(int x);//dfs=parcurgere dfs a grafului
// vector<int> bfs(int x);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
// vector<int> SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
// vector<set<int>> Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
// vector<vector<int>> Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
// vector<set<int>> Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente tareconexe
// vector<pair<int,int>> Kruskal(int &cost_total);//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
// vector<int> Dijkstra(int s); //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod dat
// // la toate celelalte, folosind un heap (complexitate O(m*logn))
// vector<int> BellmanFord(int s); //metoda ce implementeaza algoritmul Bellman-Ford de determinare a drumurilor minime de la un nod dat la toate celelalte,
// //depistand ciclurile de cost negativ; algoritmul floseste o coada (complexitate O(m*n))
// int Maxflow(int S, int D);//metoda ce implementeaza algoritmul Edmonds-Karp de determinarea a fluxului maxim ce poate fi trimis printr-o
// //retea(graf orientat alea carui muchii au asociate capacitati); complexitate O(n*(m^2))
// vector<vector<int>> RoyFloyd();//metoda ce implementeaza algoritmul Roy-Floyd de determinare a matricei de drumuri minime dintr-un graf;
// //complexitate O(n^3)
// int Darb();//metoda ce returneaza diametrul arborelui(disanta dintre cele mai indepartate doua frunze ale arborelui) - complexitate O(n)
// vector<int> Ciclueuler(); //metoda ce returneaza un ciclu eulerian din graf, daca acesta exista sau -1 altfel
//};
//
//#endif //AF_LABORATOR1_GRAF_H
//
////clasa de multimi disjuncte folosita la algoritmul lui Kruskal
//class DisjointSets
//{
//private:
// int n; //numarul de noduri
// vector<int> rep; //vectorul de reprezentanti(conform cursului)
// vector<int> h; //vector ce va retine inaltimile arborilor
//
//public:
// DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
// int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
// void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si y
//
//};
//
//DisjointSets::DisjointSets(int n)
//{
// this->n = n;
// //initializam vectorul de reprezentanti si pe cel de inaltimi
// rep.resize(n+1);
// h.resize(n+1);
// for(int i=1; i<=n; ++i)
// rep[i] = i;
//};
//
//int DisjointSets::Reprezentant(int x)
//{
// //daca x este chiar radacina(adica daca el este reprezentantul sau) il returnez
// if(x == rep[x])
// return x;
// else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
// {
// //efectuam compresia asupra arborelui
// int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
// rep[x] = r;
// //returnam reprezentantul lui x
// return r;
// }
//}
//
//void DisjointSets::Reuniune(int x, int y)
//{
// //aflam rep lui x si y
// int rx = Reprezentant(x);
// int ry = Reprezentant(y);
//
// //daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
// if(rx == ry)
// return;
//
// //subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
// if(h[rx] < h[ry])
// rep[rx] = ry;
// else if(h[rx] > h[ry])
// rep[ry] = rx;
// else //au inaltimi egale caz in care inaltimea creste cu 1 dupa subordonare
// {
// rep[rx] = ry;
// h[ry]++;
// }
//
//}
//
//
////clasa Min_heap folosita la pastrarea in ordinea crescatoare a distantelor(costurilor) arcelor din graf (folosita in metoda Dijsktra)
//class Min_heap
//{
//private:
// int n; //nr de noduri din heap
// int N; //numarul de noduri distincte din heap
// vector<arc> h; //vector de arce prin care este reprezentat heap-ul
// vector<int> pozitii; //vector ce retine pe ce pozitie in heap se afla fiecare nod x
//
//public:
// Min_heap(int n); //constructor parametrizat pt heap
// arc pop(); //metoda care scoate minimul din heap(varful)
// void push(arc a); //metoda care insereaza in heap un arc
// void go_down(int i, int n); //metoda de deplasare in jos in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
// void go_up(int i); //metoda de deplasare in sus in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
// int poz_min(int i, int n); //metoda care obtine pozitia fiului minim al unui nod abia inserta in heap
// bool empty(); //metoda care testeaza daca heap-ul este gol
//};
//
//bool Min_heap::empty()
//{
// if(N==0)
// return true;
// else
// return false;
//}
//
//
//Min_heap::Min_heap(int n)
//{
// h.resize(n+1);
// pozitii.resize(n+1);
// N = 0;
//}
//
//int Min_heap::poz_min(int i, int n)
//{
// if(2*i>n) //daca nodul este frunza
// return 0;
//
// if(2*i + 1 <= n) //daca nodul nu este frunza si exista ambii descendent
// {
// if(h[2*i].distanta <= h[2*i+1].distanta)
// return 2*i;
// else
// return 2*i+1;
// }
// else //nodul nu este frunza dar am doar descendent stang
// return 2*i;
//
//}
//
//void Min_heap::go_up(int i)
//{
// if(i>1) //daca nodul nu este deja in varf
// {
// int p = i/2; //aflu parintele
// if(h[i] < h[p])
// {
// pozitii[h[i].y] = p;
// pozitii[h[p].y] = i;
// arc aux = h[p];
// h[p] = h[i];
// h[i] = aux;
// go_up(p);
// }
// }
//}
//
//void Min_heap::go_down(int i, int n)
//{
// if(i<=n/2) //daca nodul nu este deja frunz
// {
// int m = poz_min(i,n); //aflu pozitia celui mai mic dintre fii
// if(h[m] < h[i])
// {
// pozitii[h[i].y] = m;
// pozitii[h[m].y] = i;
// arc aux = h[m];
// h[m] = h[i];
// h[i] = aux;
// go_down(m, n);
// }
// }
//}
//
//arc Min_heap::pop()
//{
// pozitii[h[N].y] = 1;
// pozitii[h[1].y] = 0;
// arc aux = h[1];
// h[1] = h[N];
// h[N] = aux;
// N--;
// go_down(1, N);
// return h[N+1];
//
//}
//
//void Min_heap::push(arc a)
//{
// //daca nodul y deja exista in heap il elimin, pentru a ne asigura ca un nod nu apare de mai multe ori in heap
// if(pozitii[a.y]>0)
// {
// arc aux = h[pozitii[a.y]];
// pozitii[h[N].y] = pozitii[a.y];
// h[pozitii[a.y]] = h[N];
// h[N] = aux;
// N--;
// go_down(pozitii[a.y], N);
// }
// //adaug noul nod in heap si memorez pozitia sa
// N++;
// h[N] = a;
// pozitii[a.y] = N;
// go_up(N);
//
//}
//
//
//
//Graf::Graf(int n, int m, bool orientat, bool costuri)
//{
// this->n = n;
// this->m = m;
// this->orientat = orientat;
// this->costuri = costuri;
// la.resize(n+1);
// la_arce.resize(n+1);
//
//}
//
//
//void Graf::Add_edge(int x, int y)
//{
// la[x].push_back(y);
// if(!orientat)
// la[y].push_back(x);
//}
//
//void Graf::Add_edge_c(int x, int y, int c)
//{
// vmc.push_back(muchie_cost(x,y,c));
//}
//
//void Graf::Add_arc(int x, int y, int d)
//{
// la_arce[x].push_back(arc(y,d));
//}
//
//void Graf::dfs_rec(int x, vector<int> & parcurgere, vector<int> & vizitat)
//{
//
// vizitat[x] = true;
// //std::cout << x << " ";
// parcurgere.push_back(x);
// for(int i=0; i<la[x].size(); ++i)
// {
// int y = la[x][i];
//
// if (vizitat[y] == false)
// {
// dfs_rec(y, parcurgere, vizitat);
// tati[y]=x;
// }
// }
//}
//
//vector<int> Graf::dfs(int x)
//{
// vector<int> parcurgere;
// tati.clear();
// tati.resize(n+1);
// vector<int> vizitat(n+1, 0);
// dfs_rec(x, parcurgere, vizitat);
//
//
// return parcurgere;
//}
//
//
//vector<int> Graf::bfs(int x)
//{
// vizitat.clear();
// tati.clear();
// rezultat.clear();
// vizitat.resize(n+1);
// tati.resize(n+1);
// queue<int> q;
// q.push(x);
// vizitat[x]=1;
//
// while(!q.empty())
// {
// x = q.front();
// //std::cout << x << " ";
// rezultat.push_back(x);
// q.pop();
// for(int i=0; i<la[x].size(); ++i)
// {
// int y=la[x][i];
// if(!vizitat[y])
// {
// q.push(y);
// tati[y]=x;
// vizitat[y]=true;
// }
// }
// }
// return rezultat;
//}
//
//vector<int> Graf::SortareTop()
//{
//
// if(orientat == false)
// { cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
// return {};
// }
//
//
// //completam vector in care retinem gradele interioare ale nodurilor
// vector<int> gr_int(n+1);
// for(int i=1; i<=n; ++i)
// {
// for(int j=0; j<la[i].size(); ++j)
// ++gr_int[la[i][j]];
// }
//
// queue<int> q; //coada folosita la sortarea topologica
// //parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
// for(int i=1; i<=n; ++i)
// if(gr_int[i]==0)
// q.push(i);
//
// //parcurgem coada pentru a obtine o sortare topologica
// vector<int> rez;
// rez.reserve(n+1);
// while(!q.empty())
// {
// int x;
// //extragem un nod din coada
// x = q.front();
// q.pop();
// //scadeam gradele interioare ale nodurilor in care intra nodul curent
// for(int i=0; i<la[x].size(); ++i)
// {
// int y = la[x][i];
// --gr_int[y];
// if(gr_int[y] == 0)
// q.push(y);
// }
// rez.push_back(x);
// //cout << x << " ";
// }
// return rez;
//
//}
//
//void Graf::dfs_bcx(int x, int parinte, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe, vector<bool> & vizitat)
//{
//
// vizitat[x] = 1;
// moment[x] = timp++;
// low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
//
// //parcurg lista de adiacente a lui x
// for(int i=0; i<la[x].size(); ++i)
// {
// int z = la[x][i];
//
// if (vizitat[z] == 0)
// {
// stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
// dfs_bcx(z, x, moment, low, stiva, timp, biconexe, vizitat);
//
// //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
// if(low[x] > low[z])
// low[x] = low[z];
//
//
// //determinare componente biconexe
// if(moment[x] <= low[z]) //deci x este punct critic
// {
// set<int> componenta;
// int a, b; //capetele unei muchii
// do
// {
// muchie m=stiva.top();
// stiva.pop();
// a=m.x;
// b=m.y;
// componenta.insert(a);
// componenta.insert(b);
// }while(a!=x || b!=z);
// biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
// }
//
// }
// else //am dat de o muchie de intoarcere
// {
// if(z!=parinte) //verific ca z sa nu fie parinte al lui x
// { //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
// // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
// // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
// if (low[x] > moment[z])
// low[x] = moment[z];
// }
// }
// }
//}
//
//vector<set<int>> Graf::Biconexe()
//{
//
// vector<set<int>> biconexe; //vectorul de componente biconexe
// if(orientat == true)
// { cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
// return biconexe;
// }
//
// vector<bool> vizitat(n+1); //vector vizitat
// vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
// vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
// stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe
//
//
// int timp = 0;// timp = contor de timp pentru crearea vectorului moment
//
// //daca graful nu este conex, se analizeaza fiecare componenta conexa
// for(int i=1; i<=n; ++i)
// if(!vizitat[i])
// dfs_bcx(i,0,moment,low,stiva, timp, biconexe, vizitat);
//
//// cout << "Numarul de componente biconexe: " << biconexe.size() << "\n";
//// cout<< "Componentele biconexe sunt: \n";
//// for(int i=0; i<biconexe.size(); ++i)
//// {
//// cout << i+1 << ") ";
//// for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
//// cout << *it << " ";
//// cout << "\n";
//// }
// return biconexe;
//}
//
//void Graf::dfs_mc(int x, int parinte, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result, vector<bool> & vizitat)
//{
// vizitat[x] = 1;
// moment[x] = timp++;
// low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
//
// //parcurg lista de adiacente a lui x
// for(int i=0; i<la[x].size(); ++i)
// {
// int z = la[x][i];
//
// if (vizitat[z] == 0)
// {
// dfs_mc(z, x, moment, low, timp, result, vizitat);
//
// //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
// if(low[x] > low[z])
// low[x] = low[z];
//
//
// //daca este muchie critica o adaugam in result
// if(low[z] > moment[x])
// result.push_back({x,z});
//
// }
// else //muchie de intoarcere
// {
// if(z!=parinte && low[x] > moment[z])
// {
// low[x] = moment[z];
// }
// }
// }
//}
//
//vector<vector<int>> Graf::Muchii_critice()
//{
// vector<vector<int>> result; //vectorul de componente biconexe
// if(orientat == true)
// { cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
// return result;
// }
//
// vector<bool> vizitat(n+1); //vector vizitat
// vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
// vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
//
//
// int timp = 0;// timp = contor de timp pentru crearea vectorului moment
//
// //daca graful nu este conex, se analizeaza fiecare componenta conexa
// for(int i=1; i<=n; ++i)
// if(!vizitat[i])
// dfs_mc(i,0,moment,low, timp, result, vizitat);
//
//
//// cout << "Numarul de muchii critice: " << result.size() << "\n";
//// cout << "Muchiile critice sunt: \n";
//// for(int i=0; i<result.size(); ++i)
//// {
//// cout << i+1 << ") " << result[i][0] << " " << result[i][1] <<"\n";
//// }
// return result;
//}
//
//void Graf::dfs_ctc(int x, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe, vector<bool> & vizitat)
//{
// vizitat[x] = true;
// moment[x] = timp++;
// low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)
//
// stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
// in_stack.insert(x);
//
// //parcurg lista de adiacente a lui x
// for(int i=0; i<la[x].size(); ++i)
// {
// int z = la[x][i];
//
// if (vizitat[z] == false)
// {
// dfs_ctc(z, moment, low, stiva, in_stack, timp, tareconexe, vizitat);
//
// //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
// // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
// if(low[x] > low[z])
// low[x] = low[z];
//
// }
// else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
// {
// //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
// // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
// // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
// if (low[x] > moment[z])
// low[x] = moment[z];
// }
// }
// if(low[x]==moment[x]) //daca nodul e radacina in componenta tare_conexa curenta(am avut un circuit)
// {
// set<int> componenta;
// int y;
// do{
// y=stiva.top();
// stiva.pop();
// in_stack.erase(y);
// componenta.insert(y);
// }while(y!=x);
// tareconexe.push_back(componenta);
// }
//}
//
//vector<set<int>> Graf::Componente_Tare_Conexe()
//{
// vector<set<int>> tareconexe; //vectorul de componente tare-conexe
//
// if(orientat == false)
// { cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
// return tareconexe;
// }
// vector<bool> vizitat(n+1);
// vector<int> moment(n+1); //vector ce retine momentul in care se viziteaza prima oara un nod di graf
// vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
// stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
// set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
//
// int timp=0;
//
// //daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
// for(int j=1; j<=n; ++j)
// if(vizitat[j]==0)
// dfs_ctc(j, moment, low, stiva, in_stack, timp, tareconexe, vizitat);
//
//// cout << "Numarul de componente tareconexe: "<< tareconexe.size() << "\n";
//// cout<< "Componentele tareconexe sunt: \n";
//// for(int i=0; i<tareconexe.size(); ++i)
//// {
//// cout << i+1 << ") ";
//// for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
//// cout << *it << " ";
//// cout << "\n";
//// }
// return tareconexe;
//}
//
//vector<pair<int,int>> Graf::Kruskal(int &cost_total)
//{
// if(orientat == true)
// { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile neorientate conexe!\n";
// return {};
// }
//
// if(costuri == false)
// { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile ale caror muchii au asociate costuri!\n";
// return {};
// }
//
// //sortam vectorul de muchii crescator dupa cost(in M*logM)
// sort(vmc.begin(), vmc.end());
//
// //definim o padure de multimi disjuncte
// DisjointSets dj(n);
//
// vector<muchie> rezultat;//vectorul in care vom retine muchiile APM-ului
// rezultat.resize(n-1);//APM-ul va avea exact n-1 muchii(pt ca este arbore)
//
// int contor = 0;//variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
// cost_total = 0;
//
// for(int i=0; i<m; ++i)
// {
// //obtin extremitatiile muchiei curente
// int x = vmc[i].x;
// int y = vmc[i].y;
//
// //aflu reprezentatntii lui x si y(pt a vedea daca sunt sau nu in multimi disjuncte)
// int rx = dj.Reprezentant(x);
// int ry = dj.Reprezentant(y);
//
// //au acelasi reprezentant muchia nu este buna si trec mai departe
// if(rx == ry)
// continue;
//
// //adaug muchia curenta in rezultat(in APM)
// rezultat[contor] = muchie(x,y);
// contor++;
// cost_total+=vmc[i].cost;
//
// //daca am atins numarul de muchii necesare APM-ului ne oprim
// if(contor == n-1)
// break;
//
// //reunim multimiile lui x si y
// dj.Reuniune(x,y);
// }
// vector<pair<int,int>> rez(contor+1);
// //afisam rezultatul(APM-ul)
//// cout << "\n";
//// cout << "Costul total al APM-ului este: " << cost_total << "\n";
//// cout << "Numarul de muchii din APM este: " << n-1 << "\n";
//// cout << "Muchiile APM-ului sunt:\n";
// for(int i=0; i<contor; ++i)
// {
// rez[i].first = rezultat[i].x;
// rez[i].second = rezultat[i].y;
//
// }
// return rez;
//
//}
//
//
//vector<int> Graf::Dijkstra(int s)
//{
//
// if(costuri == false)
// { cout << "Metoda Dijkstra de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
// return {};
// }
//
// //initializare
// vector<int> d(n+1, 1000000001); //vector de distante
// vector<int> t(n+1, 0); //vectorul de tati
// d[s] = 0;
// Min_heap H(n); //declaram heapul
//
// //punem in heap distantele de la nodul de start la toate nodurile sale adiacente si actualizam tatal acestor noduri(care este chiar nodul de start)
// //impreuna cu distantele(care sunt chiar costurile muchiilor dintre nodul 1 si noduriel respective)
// for(int i=0; i<la_arce[s].size(); ++i)
// {
// H.push(la_arce[s][i]);
// d[la_arce[s][i].y] = la_arce[s][i].distanta;
// t[la_arce[s][i].y] = s;
// }
//
// //in mod repetat, pentru restul de n-1 noduri, selectez nodurile adiacente(la fiecare pas este ales nodul cu distanta cea mai mica
// //care nu a mai fost selectat)
// //cele in care se poate ajunge in ele
// while(!H.empty())
// {
// arc ac = H.pop(); //arcul curent
//
// for(int i=0; i<la_arce[ac.y].size(); ++i)
// {
// int z = la_arce[ac.y][i].y; //nodul in care s-a ajuns din nodul curent
// int nd = d[ac.y] + la_arce[ac.y][i].distanta;//noua distanta
// if(nd < d[z]) //relaxare muchie
// {
// d[z] = nd;
// t[z] = ac.y;
// H.push(arc(z,nd));
// }
// }
// }
// //cout << "Costurile drumurile minime de la nodul " << s << " la toate celelelate noduri, determinate in urma algoritmului Dijkstra sunt: ";
//// for(int i=2; i<=n; ++i)
//// if(d[i] == 1000000001)
//// cout << 0 << " ";
//// else
//// cout << d[i] << " ";
//// cout << "\n";
//
// for(int i=2; i<=n; ++i)
// if(d[i] == 1000000001)
// d[i]=0;
// return d;
//}
//
//
//vector<int> Graf::BellmanFord(int s)
//{
// if(costuri == false)
// { cout << "Metoda BellmanFord de determinare a drumurilor de cost minim este folosita doar la grafurile ale caror muchii au asociate costuri(distante)!\n";
// return {};
// }
//
// //initializare
// vector<int> d(n+1, 1000000001); //vector de distante
// vector<int> cnt(n+1, 0); //vector ce retine de cate ori un nod a fost introdus in coada(de cate ori s-a modificat pe parcursul
// // tuturor pasilor acel nod)
// vector<int> selectat(n+1, 0); //vector ce retine daca un nod a fost pus in coada sau nu(la un pas ne intereseaza doar daca unui nod
// // i se modifica distanta, nu de cate ori i se modifica distanta, asa ca nu il vom pune in coada de fiecare data cand i se modifica
// // distanta, ci doar o data)
// vector<int> t(n+1, 0); //vectorul de tati
// d[s] = 0;
// selectat[s] = 1;
// cnt[s] = 1;
//
// queue<int> q; //coada in care se vor pune nodurile ale caror disante s-au modificat(pentru optimizarea algoritmului)
// q.push(s);
//
// //fiecare iteratie a while-ului reprezinta un pas nou din algoritmul Bellman-Ford(poate avea cel mult n-1 pasi)
//
// bool circuit_negativ = false;
//
// while(!q.empty() && !circuit_negativ)
// {
// int u = q.front();
// selectat[u] = 0;
// //daca pt nodul u a fost modificata distanta de n ori oprim executia
// if(cnt[u] == n)
// {
// circuit_negativ = true;
// break;
// }
// q.pop();
//
// for (int j = 0; j < la_arce[u].size(); ++j)
// {
// int v = la_arce[u][j].y;
// int nd = d[u] + la_arce[u][j].distanta;// noua distanta folosita la eventuala relaxare
// if (nd < d[v]) //testare pentru relaxarea drumului
// {
// d[v] = nd;
// t[v] = u;
//
// if(selectat[v] == 0)
// {
// cnt[v] ++;
// selectat[v] = 1;
// q.push(v);
// }
//
// }
// }
// }
//
// //cout << "Costurile drumurile minime de la nodul " << s << " la toate celelelate noduri, determinate in urma algoritmului BellmanFord sunt: ";
//// if(circuit_negativ)
//// cout << "Ciclu negativ!";
//// else{
//// for(int i=2; i<=n; ++i)
//// if(d[i] == 1000000001)
//// cout << 0 << " ";
//// else
//// cout << d[i] << " ";
//// }
//
// if(circuit_negativ)
// return {};
// else
// {
// for(int i=2; i<=n; ++i)
// if(d[i] == 1000000001)
// d[i] = 0;
// }
// return d;
//}
//
//
//vector<vector<int>> Graf::RoyFloyd()
//{
// //doar la grafuri cu cost
//
// int inf = (1<<20);
// vector<vector<int>> md; //matricea drumurilor unui graf, folosita in algoritmul Roy-Floyd
// md.resize(n+1,vector<int>(n+1,inf));
//
//
// //construim matricea drumurilor din listele de adiacenta la_arce
// for(int i=1; i<=n; ++i)
// for(int j=0; j<la_arce[i].size(); ++j)
// if(la_arce[i][j].distanta!=0)
// md[i][j+1] = la_arce[i][j].distanta;
//
// //roy-floyd
// for(int k=1; k<=n; ++k)
// for(int i=1; i<=n; ++i)
// for(int j=1; j<=n; ++j)
// if(md[i][k] + md[k][j] < md[i][j])
// md[i][j] = md[i][k] + md[k][j];
//
// for(int i=1; i<=n; ++i)
// for(int j=1; j<=n; ++j)
// if(md[i][j] == inf || i==j)
// md[i][j] = 0;
//
// return md;
//}
//
//
//bool Graf::bfs_maxflow(int S, int D)
//{
//
// tati[D] = 0;
// //golesc vectorul vizitat la fiecare parcurgere
// vizitat.clear();
// //redimensionam vectorul vizitat si il initializam
// vizitat.resize(n+1, 0);
//
// //coada folosita in parcurgerea bfs
// queue<int> q;
//
// //punem in coada nodul de start
// q.push(S);
// tati[S] = 0;
// vizitat[S] = true;
// //cat timp coada nu este goala(mai am elemente de procesat) si nu s-a ajunj inca in destinatie
// //parcurg bfs
// while(!q.empty() && tati[D] == 0)
// {
// //luam urmatorul element din coada
// int x = q.front();
// q.pop();
//
// //ii parcurgem lista de adiacenta
// for(int i=0; i<la[x].size(); ++i)
// {
// int y = la[x][i];
//
// //daca nodul adiacent curent nu a fost vizitat si arcul de la x la y este unul nesaturat
// if(vizitat[y] == true || capacitate[x][y] == flux[x][y])
// continue;
//
// tati[y] = x;
// vizitat[y] = true;
// q.push(y);
// }
// }
//
// if(tati[D]!=0)
// return true;
// else
// return false;
//
//}
//
//
//int Graf::Maxflow(int S, int D)
//{
// //doar la grafuri orientate cu cost
//
// //golesc vectorul tati la fiecare parcurgere(pentru aflarea fiecarui drum de ameliorare)
// tati.clear();
// //redimensionam vectorul tati si il initializam
// tati.resize(n+1, 0);
//
// int rez = 0;
//
// //dimensionam si initializam matricele flux si capacitate
// flux.resize(n+1, vector<int>(n+1, 0));
// capacitate.resize(n+1, vector<int>(n+1, 0));
//
//
// //completam matricea de capacitati(capacitatile sunt luate din listel de adiacenta)
// for(int i=1; i<=n; ++i)
// for(int j=0; j<la_arce[i].size(); ++j)
// {
// int y = la_arce[i][j].y;
// capacitate[i][y] += la_arce[i][j].distanta;
// la[i].push_back(y);
// la[y].push_back(i);
// }
//
//
// //cat timp gasesc un drum de ameliorare de la sursa la destinatie
// while(bfs_maxflow(S, D))
// {
//
// for(int i=0; i<la[D].size(); ++i)
// {
// int y = la[D][i];
// if (flux[y][D] == capacitate[y][D] || !vizitat[y])
// continue;
//
// tati[D] = y;
// int a = (1<<30);
// //parcurg drumul de la D la S pentru a determina cu cat se poate modifica fluxul pe acel drum
// for (int i = D; i != S; i = tati[i])
// a = min(a, capacitate[tati[i]][i] - flux[tati[i]][i]);
//
// if (a == 0)
// continue;
// //parcurg din nou drumul pentru a face actualizarea
// for (int i = D; i != S; i = tati[i])
// {
// flux[tati[i]][i] += a;
// flux[i][tati[i]] -= a;
// }
// rez += a;
// }
// }
//
// return rez;
//}
//
//
//int Graf::Darb()
//{
// //doar la arbori(graf neorientat conex si aciclic)
// vector<int> parcurgere = bfs(1);
// parcurgere = bfs(parcurgere[n-1]);
// int diametru=0;
// int i = parcurgere[n-1];
// do
// {
// diametru+=1;
// i = tati[i];
// }while(i!=0);
//
// return diametru;
//}
//
//
//vector<int> Graf::Ciclueuler()
//{
//
// //verificam daca toate nodurile au grade pare(daca nu returnam -1)
// for(int i=1; i<=n; ++i)
// {
// if(la_arce[i].size()%2 != 0)
// return {-1};
//
// }
// vector<int> rezultat;
//
// bool mv[m]; //vector ce retine pt fiecare muchie daca a fost sau nu vizitata
//
// //declaram stiva si punem in ea primul nod vizitat
// stack<int> s;
// s.push(1);
//
// //cat timp stiva nu e goala(mai avem elemente de procesat)
// while(!s.empty())
// {
// //extragem nod din stiva
// int nod = s.top();
// //daca acesta mai are vecini
// if(!la_arce[nod].empty())
// {
// //extragem un vecin
// int y = la_arce[nod].back().y;
// int poz = la_arce[nod].back().distanta;
// la_arce[nod].pop_back();
// //stergem muchia dintre nodul curent si vecinul sau(din ambele liste de adiacenta)
// if(!mv[poz])
// {
// mv[poz] = true;
// s.push(y);
// }
//
// }
// else
// {
// s.pop();
// rezultat.push_back(nod);
//
// }
//
// }
// //scoatem ultimul nod deoarece apare si la inceputul lantului
// rezultat.pop_back();
// return rezultat;
//}
//
//const int NMAX = 100005, MMAX = 500005;
//Graf g(NMAX,MMAX,0,0);
//
//
//int main()
//{
// int n,m,x,y;
// fin >> n >> m;
//
// for(int i=1; i<=m; ++i)
// {
// fin >> x >> y;
// g.Add_arc(x, y, i);
// g.Add_arc(y, x, i);
//
// }
//
// vector<int> rezultat;
// rezultat = g.Ciclueuler();
//
// for(int i=0; i<rezultat.size(); ++i)
// fout << rezultat[i] << " ";
// return 0;
//}
Ioan Ionescu ionut31