#include <bits/stdc++.h>
using namespace std;
const int NMAX = numeric_limits<int>::max();
class Graf {
int nrNoduri, nrMuchii;
vector<vector<int>> vecini;
int Flux_maxim(const vector<vector<int>>& cap, const int sursa, const int dest);
bool construieste_lant_nesat_BF(const int sursa, const int dest, vector<int>& tata,const vector<vector<int>>& cap, vector<vector<int>>& flux);
int diametru_arbore();
vector<vector<int>> Roy_Floyd(vector<vector<int>> matrice);
vector<int> BFS(const int Start);
vector<int> DFS(const int Start);
vector<int> distante_BFS(const int Start); // calculeaza distanta de la start la fiecare nod
void parcurgere_DFS(const int nod_curent, vector<int>& sol, vector<bool>& viz); //functie ajutatoare pentru DFS
vector<int> sortare_topologica(vector<int> grad_intern);
vector<vector<int>> ctc();
void tarjan(int nod_curent, vector<bool>& viz, vector<bool>& pe_stiva, vector<int>& low, stack<int>& stiva, vector<vector<int>>& sol);
vector<int> Dijkstra(const vector<vector<pair<int, int>>> &lista_ad, const int sursa);
vector<pair<int,int>> Prim(const vector<vector<pair<int, int>>> &lista_ad, int& cost_arbore, const int sursa);
vector<int> Bellman_Ford(const vector<vector<pair<int, int>>>&, const int sursa, bool& ciclu_negativ);
void reuneste(int x, int y, vector<int>& tata, vector<int>& inaltime); // pentru Paduri_de_multimi_disjuncte
int reprez(int x, vector<int>& tata); // pentru Paduri_de_multimi_disjuncte
bool Havel_Hakimi(int grad[]);
void afis_lista_ad();
void euler(const int nod, vector<vector<pair<int,int>>>& lista_ad, vector<bool>& viz, vector<int>& ciclu);
public:
vector<int> ciclu_eulerian(vector<vector<pair<int,int>>>& lista_ad, const int sursa);
bool este_conex();
void problema_BFS();
void problema_DFS();
void problema_sortaret();
void problema_Havel_Hakimi();
void problema_APM();
void Paduri_de_multimi_disjuncte();
void problema_Dijkstra();
void problema_Bellman_Ford();
void problema_Roy_Floyd();
void problema_darb();
void problema_ctc();
void problema_Flux_Maxim();
void problema_Ciclu_Eulerian();
};
bool Graf::este_conex()
{
bool conex = true;
vector<int> elem_dfs = DFS(1);
if(int(elem_dfs.size()) != nrNoduri)
conex = false;
return conex;
}
void Graf::euler(const int nod, vector<vector<pair<int,int>>>& lista_ad, vector<bool>& viz, vector<int>& ciclu)
{
ciclu.push_back(nod);
while(!lista_ad[nod].empty()) {
int nr_vecini = int(lista_ad[nod].size());
int vecin = lista_ad[nod][nr_vecini - 1].first;
int nr_muchie = lista_ad[nod][nr_vecini - 1].second;
lista_ad[nod].pop_back();
if(!viz[nr_muchie]) {
viz[nr_muchie] = true;
euler(vecin, lista_ad, viz, ciclu);
}
}
}
vector<int> Graf::ciclu_eulerian(vector<vector<pair<int,int>>>& lista_ad, const int sursa)
{
vector<int> ciclu;
vector<bool> viz(nrMuchii+1, false);
if(!este_conex()) // daca graful nu este conex
return ciclu;
for(int i=1; i<=nrNoduri; i++) {
if(int(vecini[i].size()) % 2 == 1){ // daca un nod are gradul impar graful nu este eulerian
return ciclu;
}
}
euler(sursa, lista_ad, viz, ciclu);
ciclu.pop_back();
return ciclu;
}
void Graf::problema_Ciclu_Eulerian()
{
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
in>>nrNoduri>>nrMuchii;
vector<vector<pair<int,int>>> lista_ad(nrNoduri+1);
vecini.resize(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y;
in>>x>>y;
lista_ad[x].push_back({y, i});
lista_ad[y].push_back({x, i});
vecini[x].push_back(y);
vecini[y].push_back(x);
}
vector<int> sol = ciclu_eulerian(lista_ad, 1);
if(sol.empty())
out << -1;
else
for(auto el: sol)
out << el << ' ';
in.close();
out.close();
}
bool Graf::construieste_lant_nesat_BF(const int sursa, const int dest, vector<int>& tata,const vector<vector<int>>& cap, vector<vector<int>>& flux)
{
queue<int> coada; // pentru BFS
bool am_ajuns = false; // bool care verifica daca BFS a ajuns la nodul destinatie
for(int i=1; i<=nrNoduri; i++){
tata[i] = 0;
}
tata[sursa] = -1; // pentru a marca nodul sursa vizitat
coada.push(sursa);
while(!coada.empty()){
int i = coada.front();
coada.pop();
if(i == dest){
am_ajuns = true;
continue;
}
for(int &j: vecini[i]){
if((cap[i][j] - flux[i][j] > 0) && tata[j] == 0){
coada.push(j);
tata[j] = i;
}
}
}
return am_ajuns;
}
int Graf::Flux_maxim(const vector<vector<int>>& cap, const int sursa, const int dest)
{
vector<int> tata(nrNoduri+1, 0);
vector<vector<int>> flux(nrNoduri+1, vector<int>(nrNoduri+1, 0));
int flux_max = 0;
/*for(int i=1; i<=nrNoduri; i++){
for(int j=1; j<= nrNoduri; j++){
cout<<cap[i][j]<<' ';
}
cout<<'\n';
}*/
// Algoritm Edmonds-Karp
// O(n * m^2)
while(construieste_lant_nesat_BF(sursa, dest, tata, cap, flux)){
for(auto &nod: vecini[dest]){ // Revizuim toate drumurile gasite de la sursa la destinatie dupa o parcurgere BF
int u = dest;
int update_flux = NMAX;
if(tata[nod] == 0){
continue;
}
tata[dest] = nod;
while(u != sursa){
update_flux = min(update_flux, cap[tata[u]][u] - flux[tata[u]][u]);
u = tata[u];
}
u = dest;
while(u != sursa){ // Revizuieste flux lant
flux[tata[u]][u] += update_flux;
flux[u][tata[u]] -= update_flux;
u = tata[u];
}
flux_max += update_flux;
/*cout<<'\n';
for(int i=1; i<=nrNoduri; i++){
for(int j=1; j<= nrNoduri; j++)
cout<<flux[i][j]<<' ';
cout<<'\n';
}*/
}
}
return flux_max;
}
void Graf::problema_Flux_Maxim()
{
ifstream in("maxflow.in");
ofstream out("maxflow.out");
in>>nrNoduri>>nrMuchii;
vector<vector<int>> cap(nrNoduri+1, vector<int>(nrNoduri+1, 0)); //matrice cu capacitati
vecini.resize(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y,z;
in>>x>>y>>z;
vecini[x].push_back(y);
vecini[y].push_back(x);
cap[x][y] = z;
}
int maxflow = Flux_maxim(cap, 1, nrNoduri);
out<<maxflow;
in.close();
out.close();
}
int Graf::diametru_arbore()
{
vector<int> bfs = BFS(1);
vector<int> dist = distante_BFS(bfs[nrNoduri-1]); //calculam distantele nodurilor de la ultimul nod gasit in bfs
int sol = 0;
for(int i=1; i<=nrNoduri; i++){ //determinam distanta dintre ultimul nod din bfs si cel mai indepartat nod de el
if(dist[i]+1 > sol)
sol = dist[i]+1;
}
return sol;
}
void Graf::problema_darb()
{
ifstream in("darb.in");
ofstream out("darb.out");
in>>nrNoduri;
vecini.resize(nrNoduri+1);
for(int i=1;i<nrNoduri;i++){
int x,y;
in>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
int sol = diametru_arbore();
out<<sol;
in.close();
out.close();
}
void Graf::problema_Roy_Floyd()
{
ifstream in("royfloyd.in");
ofstream out("royfloyd.out");
in>>nrNoduri;
vector<vector<int>> matrice(nrNoduri);
for(int i=0; i<nrNoduri; i++){
for(int j=0; j<nrNoduri; j++){
int x;
in>>x;
matrice[i].push_back(x);
}
}
vector<vector<int>> sol = Roy_Floyd(matrice);
for(int i=0; i<nrNoduri; i++){
for(int j=0; j<nrNoduri; j++){
out<< sol[i][j]<<' ';
}
out<<'\n';
}
in.close();
out.close();
}
vector<vector<int>> Graf::Roy_Floyd(vector<vector<int>> matrice) // O(n^3)
{
for(int i=0; i<nrNoduri; i++){
for(int j=0; j<nrNoduri; j++){
if(matrice[i][j] == 0 && i!=j) //daca nu exista muchie intre i si j
matrice[i][j] = 1e9;
}
}
for(int k=0; k<nrNoduri; k++){
for(int i=0; i<nrNoduri; i++){
for(int j=0; j<nrNoduri; j++){
if (matrice[i][k] + matrice[k][j] < matrice[i][j])
matrice[i][j] = matrice[i][k] + matrice[k][j];
}
}
}
for(int i=0; i<nrNoduri; i++){
for(int j=0; j<nrNoduri; j++){
if(matrice[i][j] == 1e9)
matrice[i][j] = 0;
}
}
return matrice;
}
void Graf::afis_lista_ad()
{
for(int i=1; i<=nrNoduri; i++)
{
cout<< i <<": ";
int l = vecini[i].size();
for(int j=0; j<l; j++)
{
cout<< vecini[i][j] <<' ';
}
cout<<"\n";
}
}
vector<int> Graf::distante_BFS(const int Start) // O(n+m)
{
queue<int> coada;
vector<int> dist(nrNoduri+1, 0);
vector<bool> vizitat(nrNoduri+1, false);
coada.push(Start);
vizitat[Start] = true;
while(!coada.empty()) {
int nod_curent = coada.front();
coada.pop();
for(int i=0; i< int(vecini[nod_curent].size()); i++) {
int x = vecini[nod_curent][i];
if(!vizitat[x]) {
vizitat[x] = true;
coada.push(x);
dist[x] = dist[nod_curent] + 1;
}
}
}
for(int i=1; i<=nrNoduri; i++) {
if(dist[i] == 0 && i != Start)
dist[i] = -1;
}
return dist;
}
vector<int> Graf::BFS(const int Start) // O(n+m)
{
vector<int>sol;
queue<int> coada;
vector<bool> vizitat(nrNoduri+1, false);
coada.push(Start);
vizitat[Start] = true;
while(!coada.empty()) {
int nod_curent = coada.front();
coada.pop();
sol.push_back(nod_curent);
for(int i=0; i< int(vecini[nod_curent].size()); i++) {
int x = vecini[nod_curent][i];
if(!vizitat[x]) {
vizitat[x] = true;
coada.push(x);
}
}
}
return sol;
}
void Graf::problema_BFS()
{
ifstream in("bfs.in");
ofstream out("bfs.out");
int Start;
in>>nrNoduri>>nrMuchii>>Start;
vecini.resize(nrNoduri+1);
for(int i=0; i<nrMuchii; i++)
{
int x,y;
in>>x>>y;
vecini[x].push_back(y);
}
vector<int> distante = distante_BFS(Start);
for(int i=1; i<=nrNoduri; i++) {
out << distante[i]<< ' ';
}
in.close();
out.close();
}
void Graf::parcurgere_DFS(const int nod_curent, vector<int>& sol, vector<bool>& viz)
{
viz[nod_curent] = true;
sol.push_back(nod_curent);
for(int i=0; i<int(vecini[nod_curent].size()); i++) {
int nod = vecini[nod_curent][i];
if(!viz[nod]) {
parcurgere_DFS(nod, sol , viz);
}
}
}
vector<int> Graf::DFS(const int Start) // O(n+m)
{
vector<int> sol;
vector<bool> viz(nrNoduri+1, false);
parcurgere_DFS(Start, sol, viz);
return sol;
}
void Graf::problema_DFS()
{
ifstream in("dfs.in");
ofstream out("dfs.out");
in>>nrNoduri>>nrMuchii;
vecini.resize(nrNoduri+1);
for(int i=0; i<nrMuchii; i++){
int x,y;
in>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
vector<int> nr_comp_conexa(nrNoduri+1, 0);
int sol = 0;
for(int i=1; i<=nrNoduri; i++){
if(nr_comp_conexa[i] == 0){
sol++;
vector<int> dfs = DFS(i);
for(int i=0; i<int(dfs.size()); i++){
nr_comp_conexa[dfs[i]] = sol;
}
}
}
out<<sol;
in.close();
out.close();
}
vector<int> Graf::sortare_topologica(vector<int> grad_intern)
{
vector<int> sol;
int contor = 0;
while(contor < nrNoduri) {
for(int nod = 1; nod <= nrNoduri; nod++) {
if(grad_intern[nod] == 0) { //selectam nodurile cu gradul intern 0
contor++;
sol.push_back(nod);
for(int i=0; i<int(vecini[nod].size()); i++){ //updatam gradul intern al vecinilor dupa ce am scos nodul selectat
grad_intern[vecini[nod][i]]--;
}
grad_intern[nod]--;
}
}
}
return sol;
}
void Graf::problema_sortaret()
{
ifstream in("sortaret.in");
ofstream out("sortaret.out");
in>>nrNoduri>>nrMuchii;
vecini.resize(nrNoduri+1);
vector<int> grad_intern(nrNoduri+1, 0);
for(int i=0; i<nrMuchii; i++){
int x,y;
in>>x>>y;
vecini[x].push_back(y);
grad_intern[y]++;
}
vector<int> sol = sortare_topologica(grad_intern);
for(int i=0; i<nrNoduri; i++){
out<<sol[i]<<' ';
}
in.close();
out.close();
}
bool Graf::Havel_Hakimi(int grad[])
{
int suma=0;
for(int i=0; i<nrNoduri; i++) {
suma += grad[i];
if(grad[i] > (nrNoduri - 1)) {
return false;
}
}
if(suma % 2 == 1){
return false;
}
sort(grad, grad+nrNoduri, greater<int>());
while(grad[0] != 0){
for(int i=1; i<=grad[0]; i++){
grad[i]--;
if(grad[i] < 0){
return false;
}
}
grad[0] = 0;
sort(grad, grad+nrNoduri, greater<int>());
}
return true;
}
void Graf::problema_Havel_Hakimi()
{
cout<<"Introduceti numarul de noduri: ";
cin>>nrNoduri;
int grad[nrNoduri+1];
cout<<"Introduceti " << nrNoduri <<" numere: ";
for(int i=0; i<nrNoduri; i++) {
cin >> grad[i];
}
bool HH = Havel_Hakimi(grad);
if(HH)
cout<<"DA";
else cout<<"NU";
}
void Graf::reuneste(int x, int y, vector<int>& tata, vector<int>& inaltime)
{
int rx = reprez(x, tata), ry = reprez(y, tata);
if(inaltime[rx] > inaltime[ry]) {
tata[ry] = rx;
}
else {
tata[rx] = ry;
if(inaltime[rx] == inaltime[ry])
inaltime[ry]++;
}
}
int Graf::reprez(int x, vector<int>& tata)
{
if(tata[x] == 0)
return x;
tata[x] = reprez(tata[x], tata);
return tata[x];
}
void Graf::Paduri_de_multimi_disjuncte()
{
ifstream in("disjoint.in");
ofstream out("disjoint.out");
int nrOperatii;
in>>nrNoduri>>nrOperatii;
vector<int> tata(nrNoduri+1, 0), inaltime(nrNoduri+1, 0);
// fiecare multime este memorata sub forma unui arbore, avand ca reprezentant radacina
for(int i=0;i<nrOperatii;i++) {
int operatie,x,y;
in >> operatie >> x >> y;
if(operatie == 1) {
reuneste(x, y, tata, inaltime);
}
else if(operatie == 2) {
if(reprez(x, tata) == reprez(y, tata))
out <<"DA\n";
else out<<"NU\n";
}
}
in.close();
out.close();
}
vector<pair<int,int>> Graf::Prim(const vector<vector<pair<int, int>>> &lista_ad, int& cost_arbore, const int sursa) // O(m * log(n))
{
vector<bool> viz(nrNoduri+1, false);
vector<int> tata(nrNoduri+1, -1), cost_min(nrNoduri+1, NMAX);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, sursa});
cost_min[sursa] = 0;
while(!q.empty()){
int nod = q.top().second;
int cost_muchie = q.top().first;
q.pop();
if(!viz[nod]){ // alegem muchia cea mai mica care pleaca din componenta conexa si se termina in afara ei
// nodul proaspat unit devine parte din componenta conexa
viz[nod] = true;
cost_arbore += cost_muchie;
for(auto vecin: lista_ad[nod]){ // parcurgem muchiile nodului nou
int nod_vecin = vecin.first;
int cost_vecin = vecin.second;
if(!viz[nod_vecin] && cost_min[nod_vecin] > cost_vecin){ //daca nu am vizitat nodul si muchia gasita are un cost mai bun
cost_min[nod_vecin] = cost_vecin; //updatam costul minim si introducem costul si nodul nou in coada cu prioritati
q.push({cost_vecin, nod_vecin});
tata[nod_vecin] = nod;
}
}
}
}
vector<pair<int,int>> sol;
for(int i=1; i<=nrNoduri; i++){
sol.push_back({tata[i],i});
}
return sol;
}
void Graf::problema_APM()
{
ifstream in("apm.in");
ofstream out("apm.out");
in>>nrNoduri>>nrMuchii;
vector<vector<pair<int, int>>> lista_ad(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y,cost;
in>>x>>y>>cost;
lista_ad[x].push_back({y, cost});
lista_ad[y].push_back({x, cost});
}
/*for(int i=1; i<=nrNoduri;i++){
cout<<i<<": ";
for(int j=0; j<int(lista_ad[i].size());j++){
cout<<lista_ad[i][j].first <<' ' <<lista_ad[i][j].second<<", ";
}
cout<<endl;
}*/
int cost_arbore = 0;
vector<pair<int,int>> sol = Prim(lista_ad, cost_arbore, 1);
out<<cost_arbore<<'\n'<<nrNoduri-1<<'\n';
for(int i=1; i<=nrNoduri-1; i++){
out<<sol[i].first<<' '<<sol[i].second<<'\n';
}
in.close();
out.close();
}
vector<int> Graf::Dijkstra(const vector<vector<pair<int, int>>>& lista_ad, const int sursa) // O(m * log(n))
{
vector<int> dist(nrNoduri+1, NMAX);
vector<bool> viz(nrNoduri+1, false);
dist[sursa] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, sursa});
while(!q.empty()){
int nod = q.top().second;
q.pop();
if(!viz[nod]){
viz[nod] = true;
for(auto vecin: lista_ad[nod]){ //parcurgem toti vecinii nodului curent
int nod_vecin = vecin.first;
int cost_vecin = vecin.second;
if(dist[nod] + cost_vecin < dist[nod_vecin]){ //actualizam distantele
dist[nod_vecin] = dist[nod] + cost_vecin;
q.push({dist[nod_vecin], nod_vecin});
}
}
}
}
return dist;
}
void Graf::problema_Dijkstra()
{
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
in>>nrNoduri>>nrMuchii;
vector<vector<pair<int, int>>> lista_ad(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y,cost;
in>>x>>y>>cost;
lista_ad[x].push_back(make_pair(y, cost));
}
/*for(int i=1; i<=nrNoduri;i++){
cout<<i<<": ";
for(int j=0; j<int(lista_ad[i].size());j++){
cout<<lista_ad[i][j].first <<' ' <<lista_ad[i][j].second<<", ";
}
cout<<endl;
}*/
vector<int> sol = Dijkstra(lista_ad, 1);
for(int i=2; i<=nrNoduri; i++){
if(sol[i]==NMAX)
out<<"0 ";
else
out<<sol[i]<<' ';
}
in.close();
out.close();
}
vector<int> Graf::Bellman_Ford(const vector<vector<pair<int, int>>> &lista_ad, const int sursa, bool& ciclu_negativ) // O(n*m)
{
vector<int> dist(nrNoduri+1, NMAX), viz(nrNoduri+1, 0);
dist[sursa] = 0;
ciclu_negativ = false;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, sursa});
while(!q.empty()){
int nod = q.top().second;
q.pop();
viz[nod]++;
if (viz[nod] == nrNoduri){ // daca se mai fac actualizari la pasul n, inseamna ca exista un ciclu negativ in graf
dist.resize(0);
ciclu_negativ = true;
break;
}
for(auto vecin: lista_ad[nod]){ //parcurgem toti vecinii nodului curent
int nod_vecin = vecin.first;
int cost = vecin.second;
if(dist[nod] + cost < dist[nod_vecin]){ //relaxam muchia
dist[nod_vecin] = dist[nod] + cost;
q.push({dist[nod_vecin], nod_vecin});
}
}
}
return dist;
}
void Graf::problema_Bellman_Ford()
{
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
in>>nrNoduri>>nrMuchii;
vector<vector<pair<int, int>>> lista_ad(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y,cost;
in>>x>>y>>cost;
lista_ad[x].push_back({y, cost});
}
/*for(int i=1; i<=nrNoduri;i++){
cout<<i<<": ";
for(int j=0; j<int(lista_ad[i].size());j++){
cout<<lista_ad[i][j].first <<' ' <<lista_ad[i][j].second<<"; ";
}
cout<<endl;
}*/
bool ciclu_negativ;
vector<int> sol = Bellman_Ford(lista_ad, 1, ciclu_negativ);
if(ciclu_negativ){
out<<"Ciclu negativ!";
}
else{
for(int i=2; i<=nrNoduri; i++){
out<<sol[i]<<' ';
}
}
in.close();
out.close();
}
void Graf::tarjan(int nod_curent, vector<bool>& viz, vector<bool>& pe_stiva, vector<int>& low, stack<int>& stiva, vector<vector<int>>& sol)
{
viz[nod_curent] = true;
stiva.push(nod_curent);
pe_stiva[nod_curent] = true;
for(int i=0; i<int(vecini[nod_curent].size()); i++){
int vecin = vecini[nod_curent][i];
if(!viz[vecin]){
tarjan(vecin, viz, pe_stiva, low, stiva, sol);
}
if(pe_stiva[vecin]){
low[vecin] = min(low[vecin], low[nod_curent]);
}
}
/*if(low[nod_curent] == nod_curent){
vector<int> componenta_conexa;
int x = stiva.top();
while(low[x] == nod_curent){
componenta_conexa.push_back(x);
pe_stiva[x] = false;
stiva.pop();
x = stiva.top();
}
sol.push_back(componenta_conexa);
}*/
}
vector<vector<int>> Graf::ctc()
{
stack<int> stiva;
vector<bool> viz(nrNoduri+1, false), pe_stiva(nrNoduri+1, false);
vector<int> low(nrNoduri+1);
vector<vector<int>> sol;
for(int i=1; i<=nrNoduri; i++){
low[i] = i;
}
tarjan(1, viz, pe_stiva, low, stiva, sol);
/*for(int i=0; i<int(sol.size()); i++){
for(int j=0; j<int(sol[i].size()); j++){
cout<<sol[i][j]<<' ';
}
cout<<'\n';
}*/
return sol;
}
void Graf::problema_ctc()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in>>nrNoduri>>nrMuchii;
vecini.resize(nrNoduri+1);
for(int i=1; i<=nrMuchii; i++){
int x,y;
in>>x>>y;
vecini[x].push_back(y);
}
afis_lista_ad();
vector<vector<int>> sol;
ctc();
in.close();
out.close();
}
int main()
{
Graf G;
//G.problema_BFS();
//G.problema_DFS();
//G.problema_ctc();
//G.problema_sortaret();
//G.problema_Havel_Hakimi();
//G.problema_APM();
//G.Paduri_de_multimi_disjuncte();
//G.problema_Dijkstra();
//G.problema_Bellman_Ford();
//G.problema_Roy_Floyd();
//G.problema_darb();
//G.problema_Flux_Maxim();
G.problema_Ciclu_Eulerian();
return 0;
}