#include <iostream>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
class Graf
{
private:
int nr_noduri;
public:
//constructori
Graf();
Graf(int nr_noduri);
//operatorii de copiere
Graf(const Graf& g);
Graf& operator=(const Graf& g);
//functiile de cititre si afisare
friend ifstream& operator>>(ifstream& in,Graf& g);
//destructorul
~Graf();
//functie virtuala pura
virtual string tip_graf()=0;
//setteri si getteri
int get_nr_noduri();
//citire si afisare virtuala
virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);
};
int Graf::get_nr_noduri()
{
return this->nr_noduri;
}
Graf::Graf()
{
this -> nr_noduri = 0;
}
Graf::Graf(int nr_noduri)
{
this -> nr_noduri = nr_noduri;
}
Graf::Graf(const Graf& g)
{
this -> nr_noduri = g.nr_noduri;
}
Graf& Graf::operator=(const Graf& g)
{
if(this != &g)
{
this -> nr_noduri = g.nr_noduri;
}
return *this;
}
ifstream& Graf::citire_graf_virtuala_fisier(ifstream& in)
{
in>>this -> nr_noduri;
return in;
}
ifstream& operator>>(ifstream& in,Graf& g)
{
return g.citire_graf_virtuala_fisier(in);
}
Graf::~Graf(){};
class Graf_Neorientat:public Graf
{
private:
int numar_muchii;
unordered_map<int,vector<int>>lista_adiacenta;
//functie ajutatoare pentru a afla muchiile critice dintr-un graf
static void dfs_muchie_critica(int n,int nod,int nivel,unordered_map<int,vector<int>> lista_adiacenta1,vector<int> &viz,vector<int> &lista_intoarcere,vector<int> &lista_nivel,vector<int> &mat,vector<int> &lista_tati);
//functii ajutatoare pentru a afla componentele biconexe ale unui graf
void dfs_biconex(int nod_start,int nivel,vector<int> &viz,vector<int> &lista_intoarcere,vector<int> &lista_nivel,vector<int> &mat,unordered_map<int,vector<int>> &lista_fii);
void dfs_biconex_stiva(int nod_start,vector<int> &viz,vector<int> lista_intoarcere,vector<int> lista_nivel,vector<int> lista_noduri_critice,vector<set<int,less<int>>> &solutie,stack<pair<int,int>> &stiva_muchii);
//functie ajutatoare pentru a afla cate componente conexe are un graf
void dfs(int nod, vector<int> &viz);
public:
//constructori
Graf_Neorientat();
Graf_Neorientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta);
//operatorii de copiere
Graf_Neorientat(const Graf_Neorientat& g);
Graf_Neorientat& operator=(const Graf_Neorientat& g);
//functiile de cititre si afisare
friend ifstream& operator>>(ifstream& in,Graf_Neorientat& g);
//destructorul
~Graf_Neorientat();
//functii
static bool havel_hakimi(vector<int> grade);
vector<set<int,less<int>>> begin_biconex();
string tip_graf();
int begin_dfs();
static vector<vector<int>> muchii_critice(int n,vector<vector<int>> muchii);
//getteri
int get_nr_muchii();
unordered_map<int,vector<int>> get_lista_adiacenta();
//citire si afisare virtuala
virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);
};
void Graf_Neorientat::dfs_muchie_critica(int n,int nod,int nivel,unordered_map<int,vector<int>> lista_adiacenta1,vector<int> &viz,vector<int> &lista_intoarcere,vector<int> &lista_nivel,vector<int> &mat,vector<int> &lista_tati)
{
viz[nod]=1;//marcam nodul ca fiind vizitat
lista_nivel[nod]=nivel;//initializam nivelul nodului
lista_intoarcere[nod]=nivel;//initializam nivelul de intoarcere al nodului cu nivelul curent
if(lista_adiacenta1.find(nod)!=lista_adiacenta1.end())//daca nodul curent are vecini ii parcurgem
{
for(int i=0; i<lista_adiacenta1[nod].size(); i++)
if(viz[lista_adiacenta1[nod][i]]==0)//gasit un vecin nevizitat
{
mat[lista_adiacenta1[nod][i]*n + nod] = 1;//notam muchia in matricea mat ca fiind vizitata pentru a retine daca face pare din arborele dfs
mat[nod*n + lista_adiacenta1[nod][i]] =1;
lista_tati[lista_adiacenta1[nod][i]]=nod;//notam tatal nodului pe care urmeaza sa il vizitam
dfs_muchie_critica(n,lista_adiacenta1[nod][i],nivel+1,lista_adiacenta1,viz,lista_intoarcere,lista_nivel,mat,lista_tati);//apelam dfs pentru vecin
lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta1[nod][i]]);//la final actualizam nivelul de intoarecere al nodului curent
}
else//daca vecinul este vizitat
{
if(mat[nod*n + lista_adiacenta1[nod][i]]==0)//daca muchia catre vecin nu face parete din arborele dfs inseamna ca muchia aceasta este de intoarcere
lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta1[nod][i]]);//actualizam nivelul de intoarcere
}
}
}
vector<vector<int>> Graf_Neorientat::muchii_critice(int n,vector<vector<int>> connections)
{
unordered_map<int,vector<int>>lista_adiacenta1;//lista de vecini pentru fiecare nod
for(int i=0; i<connections.size(); i++)
{
lista_adiacenta1[connections[i][0]].push_back(connections[i][1]);
lista_adiacenta1[connections[i][1]].push_back(connections[i][0]);
}
vector<int> viz(n,0);//vectorul ce retine daca un nod a fost vizitat sau nu
vector<int> lista_nivel(n,0);//vectorul ce retine nivelul din arborele dfs al fiecarui nod
vector<int> lista_intoarcere(n,0);//vectorul ce retine nivelul de intoarecere al fiecarui nod
vector<int> mat(n*n,0);//matricea ce retine daca o muchie face parte sau nu din arborele dfs
vector<int> lista_tati(n,-1);//vectorul ce retine tatal fiecarui nod din arborele dfs
dfs_muchie_critica(n,0,0,lista_adiacenta1,viz,lista_intoarcere,lista_nivel,mat,lista_tati);//apelam dfs_muchie_critica pentru a actualiza valorile vectorilor de mai sus
vector<vector<int>> solutie;//vectorul in care vom retine solutia
for(int i=0; i<connections.size(); i++)//parcurgem vectorul de muchii
{
if(lista_tati[connections[i][1]]==connections[i][0])//daca primul nod este tatal
{
if(lista_intoarcere[connections[i][1]]>lista_nivel[connections[i][0]])//daca nivelul de intoarcere al fiului este mai mare decat nivelul tatalui
{
//muchia este crtica si o introducem in solutie
vector<int> muchie_critica;
muchie_critica = connections[i];
solutie.push_back(muchie_critica);
}
}
else if(lista_tati[connections[i][0]]==connections[i][1])//daca al doilea nod este tatal
{
if(lista_intoarcere[connections[i][0]]>lista_nivel[connections[i][1]])//daca nivelul de intoarcere al fiului este mai mare decat nivelul tatalui
{
//muchia este critica si o introducem in solutie
vector<int> muchie_critica;
muchie_critica = connections[i];
solutie.push_back(muchie_critica);
}
}
}
return solutie;//returnam solutia
}
bool Graf_Neorientat::havel_hakimi(vector<int> grade)
{
if(grade[0]>=grade.size())//daca primul grad este mai mare decat numarul de noduri-1 atunci este clar ca nu se poate scrie un graf cu aceste grade
return false;
else if(grade[0]==0)//daca primul grad = 0 verificam daca toate celelalte grade sunt 0
{
int ok=1;
for(int i=0;i<grade.size();i++)
if(grade[i]!=0)
ok=0;
if(ok==1)
return true;//daca toate celelalte grade sunt 0 => exista un graf cu aceste grade
else
return false;//daca exista un grad care nu este 0 inseamna ca este un nod care are grad < 0 deci returnam false
}
else//altfel eliminam primul element si scadem 1 din primele grade[0] noduri si repetam algoritmul
{
int grad1 =grade[0];
for(int i=1;i<grade.size();i++)
{
if(i<=grad1)
grade[i]--;
grade[i-1]=grade[i];
}
grade.pop_back();
sort(grade.begin(), grade.end(), greater<int>());
return havel_hakimi(grade);
}
}
void Graf_Neorientat::dfs_biconex_stiva(int nod,vector<int> &viz,vector<int> lista_intoarcere,vector<int> lista_nivel,vector<int> lista_noduri_critice,vector<set<int,less<int>>> &solutie,stack<pair<int,int>> &stiva_muchii)
{
viz[nod] = 1;//marcam nodul ca fiind vizitat
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
{
for(int i=0;i<lista_adiacenta[nod].size();i++)//parcurgem inca o data arborele dfs
if(viz[lista_adiacenta[nod][i]] == 0)//daca gasim un vecin nevizitat
{
pair<int,int> muchie_curenta;
muchie_curenta.first = nod;
muchie_curenta.second = lista_adiacenta[nod][i];
stiva_muchii.push(muchie_curenta);//adaugam muchia in stiva
//apelam din nou dfs_biconex_stiva pentru a aduga si urmatoarele muchii in stiva
dfs_biconex_stiva(lista_adiacenta[nod][i],viz,lista_intoarcere,lista_nivel,lista_noduri_critice,solutie,stiva_muchii);
//daca nodul curent este critic si fiul sau are nivelul de intoarcere >= decat nivelul tatalui sau atunci inseamna ca toate muchile din ce urmeaza in stiva
//dupa aceasta muchie(inclusiv) alcatuiesc o componenta biconexa
if(lista_noduri_critice[muchie_curenta.first]==1 && lista_intoarcere[muchie_curenta.second]>=lista_nivel[muchie_curenta.first])
{
set<int,less<int>> componenta_biconexa;//cream un set in care sa retinem nodurile ce alcatuiesc componenta biconexa
//cat timp in varful stivei nu este muchia curenta adaugam nodurile in set
while(stiva_muchii.top().first!=muchie_curenta.first||stiva_muchii.top().second!=muchie_curenta.second)
{
componenta_biconexa.insert(stiva_muchii.top().second);
componenta_biconexa.insert(stiva_muchii.top().first);
stiva_muchii.pop();
}
//adaugam si muchia curenta
componenta_biconexa.insert(stiva_muchii.top().second);
componenta_biconexa.insert(stiva_muchii.top().first);
stiva_muchii.pop();
solutie.push_back(componenta_biconexa);//adaugam setul la vectorul solutie
}
}
}
}
void Graf_Neorientat::dfs_biconex(int nod,int nivel,vector<int> &viz,vector<int> &lista_intoarcere,vector<int> &lista_nivel,vector<int> &mat,unordered_map<int,vector<int>> &lista_fii)
{
viz[nod] = 1;//marcam nodul curent ca fiind vizitat
lista_nivel[nod] = nivel;//actualizam nivelul nodului din arborele dfs
lista_intoarcere[nod] = nivel;//initializam nivelul de intoarcere cu nivelul curent al nodului
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
{
int nr_noduri2 = Graf_Neorientat::get_nr_noduri()+1;//retinem numarul de noduri pentru a nu apela functia get_nr_noduri de prea multe ori
for(int i=0;i<lista_adiacenta[nod].size();i++)//parcurgem lista de veicini a nodului
if(viz[lista_adiacenta[nod][i]]==0)//daca gasim un vecin nevizitat
{
//cout<<nod<<" "<<lista_adiacenta[nod][i-1]<<"\n";
lista_fii[nod].push_back(lista_adiacenta[nod][i]);//il adaugam in lista de fii a nodului curent
mat[lista_adiacenta[nod][i]*nr_noduri2 + nod] = 1;//actualizam matricea ce retine muchiile ce fac parte din arborele dfs
mat[nod*nr_noduri2 + lista_adiacenta[nod][i]] =1;
dfs_biconex(lista_adiacenta[nod][i],nivel+1,viz,lista_intoarcere,lista_nivel,mat,lista_fii);//apelam dfs_biconex pentru vecin
lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta[nod][i]]);//actualizam nivelul de intoarcere al nodului curent
}
else//daca gasim un vecin vizitat
{
if(mat[nod* nr_noduri2 + lista_adiacenta[nod][i]]==0)//daca muchia nu face parte din arborele dfs => muchia este de intoarcere
lista_intoarcere[nod] = min(lista_intoarcere[nod],lista_intoarcere[lista_adiacenta[nod][i]]);//actualizam nivelul de intoarcere al nodului curent
}
}
}
vector<set<int,less<int>>> Graf_Neorientat::begin_biconex()
{
int nr_noduri2 = Graf_Neorientat::get_nr_noduri();//retinem numarul de noduri ca sa nu apelam functia get de prea multe ori
vector<int> lista_nivel(nr_noduri2+1,0);//vectorul ce retine nivelul fiecarui nod
vector<int> lista_intoarcere(nr_noduri2+1,0);//vectorul ce retine nivelul de intoarcere al fiecarui nod
vector<int> viz(nr_noduri2+1,0);//vectorul ce retine daca un nod este sau nu vizitat
vector<int> matrice_muchii_dfs((nr_noduri2+1)*(nr_noduri2+1),0);//matricea ce retine muchiile ce fac parte din arborele dfs
unordered_map<int,vector<int>> lista_fii;//hash-ul ce retine pentru fiecare nod lista de fii din arborele dfs
//functia dfs biconex actualizeaza vectorii definiti mai sus pentru a putea face operatii rapide cu ei
dfs_biconex(1,0,viz,lista_intoarcere,lista_nivel,matrice_muchii_dfs,lista_fii);
vector<int> lista_noduri_critice(nr_noduri2+1);//vectorul ce retine ce noduri sunt critice
for(int i=1;i<=nr_noduri2+1;i++)//parcurgem toate nodurile
{
if(lista_fii.find(i)!=lista_fii.end())
for(int j=0;j<lista_fii[i].size();j++)//parcugem lista de fii
if(lista_intoarcere[lista_fii[i][j]]>=lista_nivel[i])//daca pentru nodul i exista cel putin un fiu care are nivelul de intoarcere >= nivelul lui i atunci i este nod critic
{
lista_noduri_critice[i]=1;
break; //ne oprim din parcurgerea fiilor
}
}
stack<pair<int,int>> stiva_muchii_dfs_curenta;//stiva ce ne va ajuta sa retinem muchiile pe masura ce le parcurgem in arborele dfs
vector<int> viz2(nr_noduri2+1,0);//vectorul ce retine daca un nod este sau nu vizitat
vector<set<int,less<int>>> solutie;//vectorul in care vom retine solutia
//in functia dfs_biconex_stiva vom construii vecotorul solutie care este transmis prin referinta
dfs_biconex_stiva(1,viz2,lista_intoarcere,lista_nivel,lista_noduri_critice,solutie,stiva_muchii_dfs_curenta);
//returnam vectorul solutie
return solutie;
/*cout<<"Lista nivel ";
for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
cout<<i<<":"<<lista_nivel[i]<<" ";
cout<<"\n\nLista intoarcere ";
for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
cout<<lista_intoarcere[i]<<" ";
cout<<"\n\nLista noduri critice ";
for(int i=1;i<=Graf_Neorientat::get_nr_noduri();i++)
if(lista_noduri_critice[i]==1)
cout<<i<<" ";
cout<<"\n\n";*/
}
void Graf_Neorientat::dfs(int nod,vector<int> &viz)
{
viz[nod] = 1;//notam nodul curent ca fiind vizitat
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
{
for(int i=0;i<lista_adiacenta[nod].size();i++)//parcurgem toti vecinii nodului curent
if(viz[lista_adiacenta[nod][i]]==0)//daca gasim un vecin nevizitat apelam dfs de acel veci
dfs(lista_adiacenta[nod][i],viz);
}
}
int Graf_Neorientat::begin_dfs()
{
int nr_noduri2 = Graf_Neorientat::get_nr_noduri();//retinem numarul de noduri pentru a nu apela functia get de prea multe ori
vector<int> viz(nr_noduri2+1,0);//initializam vectorul ce retine daca un nod este vizitat sau nu
int contor=0;//contor va retine numarul de componente conexe
for(int i=1;i<=nr_noduri2;i++)//parcugem toate nodurile si apelam dfs pentru cele nevizitate
if(viz[i]==0)
{
contor++;//atunci cand gasim un nod nevizitat marim contorul
Graf_Neorientat::dfs(i,viz);
}
return contor;
}
string Graf_Neorientat::tip_graf()
{
return "\nGraf Neorientat";
}
int Graf_Neorientat::get_nr_muchii()
{
return this -> numar_muchii;
}
unordered_map<int,vector<int>> Graf_Neorientat::get_lista_adiacenta()
{
return this -> lista_adiacenta;
}
Graf_Neorientat::Graf_Neorientat():Graf()
{
this -> numar_muchii = 0;
}
Graf_Neorientat::Graf_Neorientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta):Graf(nr_noduri)
{
this->numar_muchii = numar_muchii;
this->lista_adiacenta = lista_adiacenta;
}
Graf_Neorientat::Graf_Neorientat(const Graf_Neorientat& g):Graf(g)
{
this -> numar_muchii = g.numar_muchii;
this -> lista_adiacenta= g.lista_adiacenta;
}
Graf_Neorientat& Graf_Neorientat::operator=(const Graf_Neorientat& g)
{
if(this!= &g)
{
Graf::operator=(g);
this->numar_muchii = g.numar_muchii;
this->lista_adiacenta = g.lista_adiacenta;
}
*this;
}
ifstream& Graf_Neorientat::citire_graf_virtuala_fisier(ifstream& in)
{
Graf::citire_graf_virtuala_fisier(in);
in>>this->numar_muchii;
for(int i=1;i<=this->numar_muchii;i++)
{
int first,second;
in>>first>>second;
lista_adiacenta[first].push_back(second);
lista_adiacenta[second].push_back(first);
}
return in;
}
ifstream& operator>>(ifstream& in,Graf_Neorientat& g)
{
return g.citire_graf_virtuala_fisier(in);
}
Graf_Neorientat::~Graf_Neorientat(){}
class Graf_Neorientat_Cost:public Graf
{
private:
int numar_muchii;
unordered_map<int,vector<pair<int,int>>> lista_adiacenta;
public:
//constructori
Graf_Neorientat_Cost();
Graf_Neorientat_Cost(int nr_noduri,int numar_muchii,unordered_map<int,vector<pair<int,int>>> lista_adiacenta);
//operatori de copiere
Graf_Neorientat_Cost(const Graf_Neorientat_Cost& g);
Graf_Neorientat_Cost& operator=(const Graf_Neorientat_Cost& g);
//functiile de citire
friend ifstream& operator>>(ifstream& in,Graf_Neorientat_Cost& g);
string tip_graf();
virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);
//getteri
unordered_map<int,vector<pair<int,int>>> get_lista_adiacenta();
int get_numar_muchii();
//functii
vector<pair<int,int>> begin_APM(int &suma_arborelui);
//destructor
~Graf_Neorientat_Cost(){}
};
class muchie_cost
{
private:
int cost,nod_1,nod_2;
public:
muchie_cost(int cost1,int nod_1,int nod_2)
{
this->cost=cost1;
this->nod_1=nod_1;
this->nod_2=nod_2;
}
friend bool operator<(const muchie_cost& m1,const muchie_cost& m2)
{
return m1.cost <= m2.cost;
}
int get_cost() const {return cost;}
int get_nod_1() const {return nod_1;}
int get_nod_2() const {return nod_2;}
};
vector<pair<int,int>> Graf_Neorientat_Cost::begin_APM(int &suma_arborelui)
{
suma_arborelui=0;
int numar_noduri = Graf::get_nr_noduri();
set<muchie_cost,less<muchie_cost>> heap;
for(int i=0;i<lista_adiacenta[1].size();i++)
{
muchie_cost m_curenta(lista_adiacenta[1][i].second,1,lista_adiacenta[1][i].first);
heap.insert(m_curenta);
}
vector<int> viz(numar_noduri+1,0);
viz[1]=1;
vector<pair<int,int>> solutie;
while(!heap.empty())
{
set<muchie_cost,less<muchie_cost>>::iterator itr;
itr=heap.begin();
if(viz[(*itr).get_nod_2()]==0)
{
viz[(*itr).get_nod_2()]=1;
suma_arborelui=suma_arborelui+(*itr).get_cost();
pair<int,int> pereche;
pereche.first=(*itr).get_nod_1();
pereche.second=(*itr).get_nod_2();
solutie.push_back(pereche);
int nod_urmator=(*itr).get_nod_2();
for(int i=0;i<lista_adiacenta[nod_urmator].size();i++)
if(viz[lista_adiacenta[nod_urmator][i].first]==0)
{
muchie_cost m_curenta(lista_adiacenta[nod_urmator][i].second,nod_urmator,lista_adiacenta[nod_urmator][i].first);
heap.insert(m_curenta);
}
heap.erase(itr);
}
else
heap.erase(itr);
}
return solutie;
}
string Graf_Neorientat_Cost::tip_graf()
{
return "Graf neorientat cu costuri";
}
unordered_map<int,vector<pair<int,int>>> Graf_Neorientat_Cost::get_lista_adiacenta()
{
return this->lista_adiacenta;
}
int Graf_Neorientat_Cost::get_numar_muchii()
{
return this->numar_muchii;
}
Graf_Neorientat_Cost::Graf_Neorientat_Cost():Graf()
{
this->numar_muchii=0;
}
Graf_Neorientat_Cost::Graf_Neorientat_Cost(int nr_noduri,int numar_muchii,unordered_map<int,vector<pair<int,int>>> lista_adiacenta):Graf(nr_noduri)
{
this->numar_muchii=numar_muchii;
this->lista_adiacenta=lista_adiacenta;
}
Graf_Neorientat_Cost::Graf_Neorientat_Cost(const Graf_Neorientat_Cost& g):Graf(g)
{
this->numar_muchii=g.numar_muchii;
this->lista_adiacenta=g.lista_adiacenta;
}
Graf_Neorientat_Cost& Graf_Neorientat_Cost::operator=(const Graf_Neorientat_Cost& g)
{
if(this!=&g)
{
Graf::operator=(g);
this->numar_muchii=g.numar_muchii;
this->lista_adiacenta=g.lista_adiacenta;
}
*this;
}
ifstream& Graf_Neorientat_Cost::citire_graf_virtuala_fisier(ifstream& in)
{
Graf::citire_graf_virtuala_fisier(in);
in>>this->numar_muchii;
for(int i=1;i<=this->numar_muchii;i++)
{
int fst,snd,cost;
in>>fst>>snd>>cost;
pair<int,int> pereche;
pereche.first = snd;
pereche.second = cost;
lista_adiacenta[fst].push_back(pereche);
pereche.first = fst;
pereche.second = cost;
lista_adiacenta[snd].push_back(pereche);
}
return in;
}
ifstream& operator>>(ifstream& in,Graf_Neorientat_Cost& g)
{
return g.citire_graf_virtuala_fisier(in);
}
class Graf_Orientat:public Graf
{
private:
int numar_muchii;
unordered_map<int,vector<int>>lista_adiacenta;
//functii ajutatoare pentru a afla componentele tare conexe
void dfs_stiva(int nod,vector<int> &viz,stack<int> &noduri);
void dfs_tare_conex(int nod,vector<int> &viz,set<int,less<int>> &componenta_tare_conexa);
public:
//constructori
Graf_Orientat();
Graf_Orientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta);
//operatorii de copiere
Graf_Orientat(const Graf_Orientat& g);
Graf_Orientat& operator=(const Graf_Orientat& g);
//functiile de cititre si afisare
friend ifstream& operator>>(ifstream& in,Graf_Orientat& g);
//destructorul
~Graf_Orientat();
//functii
string tip_graf();
vector<int> bfs(int nod_start);
vector<set<int,less<int>>> begin_componente_tare_conexe();
vector<int> begin_sortaret();
//setteri si getteri
int get_nr_muchii();
unordered_map<int,vector<int>> get_lista_adiacenta();
//citire si afisare virtuala
virtual ifstream& citire_graf_virtuala_fisier(ifstream& in);
};
string Graf_Orientat::tip_graf()
{
return "\nGraf Orientat";
}
vector<int> Graf_Orientat::begin_sortaret()
{
int numar_noduri = Graf_Orientat::get_nr_noduri();//retinem numarul de noduri pentru a nu folosi getterul de prea multe ori
vector<int> grad_interior(numar_noduri+1,0);//vector ce retine pentru fiecare nod gradul interior
for(int i=1;i<=numar_noduri;i++)//parcurgem toate nodurile si initializam gradul interior
{
if(lista_adiacenta.find(i)!=lista_adiacenta.end())
for(int j=0;j<lista_adiacenta[i].size();j++)
grad_interior[lista_adiacenta[i][j]]++;
}
queue<int> coada_noduri;//coada in care vom retine nodurile pe masura ce parcurgem graful
vector<int> viz(numar_noduri+1,0);//vector ce retine pentru fiecare nod daca a fost vizitat sau nu
for(int i=1;i<=numar_noduri;i++)//adaugam in coada toate nodurile care au gradul 0 si le marcam ca fiind vizitate
if(grad_interior[i]==0)
{
coada_noduri.push(i);
viz[i] = 1;
}
vector<int> solutie;//vectorul in care vom pastra solutia
while(!coada_noduri.empty())//cat timp coada nu este goala
{
solutie.push_back(coada_noduri.front());//adaugam primul nod din coada in solutie
if(lista_adiacenta.find(coada_noduri.front())!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[coada_noduri.front()].size();i++)//trecem prin toti vecinii nodului curent si scadem gradul interior cu 1
{
grad_interior[lista_adiacenta[coada_noduri.front()][i]]--;
if(grad_interior[lista_adiacenta[coada_noduri.front()][i]]==0)//daca gradul interior devine 0 il adaugam in coada
{
viz[lista_adiacenta[coada_noduri.front()][i]]=1;
coada_noduri.push(lista_adiacenta[coada_noduri.front()][i]);
}
}
coada_noduri.pop();//eliminam nodul de la inceput si reluam algoritmul
}
return solutie;
}
void Graf_Orientat::dfs_stiva(int nod,vector<int> &viz,stack<int> &noduri)
{
viz[nod] = 1;//notam nodul curent ca fiind vizitat
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[nod].size();i++)//parcurgem toti vecinii nodului
{
if(viz[lista_adiacenta[nod][i]]==0)//cand gasim un vecin nevizitat apelam dfs_stiva pe acel vecin
dfs_stiva(lista_adiacenta[nod][i],viz,noduri);
}
noduri.push(nod);//la final introducem in stiva nodul pentru a avea ordinea inversa parcurgerii in stiva
}
void Graf_Orientat::dfs_tare_conex(int nod,vector<int> &viz,set<int,less<int>> &componenta_tare_conexa)
{
viz[nod]=1;//notam nodul curent ca fiind vizitat
componenta_tare_conexa.insert(nod);//inseram nodul in setul ce retine componenta tare conexa
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[nod].size();i++)//parcurgem toti vecinii
{
if(viz[lista_adiacenta[nod][i]]==0)//daca gasim un vecin nevizitat apelam dfs_tare_conex din nou
dfs_tare_conex(lista_adiacenta[nod][i],viz,componenta_tare_conexa);
}
//la final functia va returna prin parametrul componenta_tare_conexa nodurile ce alcatuiesc aceasta componenta tare conexa
}
vector<set<int,less<int>>> Graf_Orientat::begin_componente_tare_conexe()
{
int numar_noduri = Graf_Orientat::get_nr_noduri();//retinem numarul de noduri pentru a nu apela functia get de prea multe ori
vector<int> viz(numar_noduri+1,0);//vectorul ce retine daca un nod a fost vizitat sau nu
vector<set<int,less<int>>> componente_conexe;//vectorul de componente conexe ce va fi returnat la final
for(int k=1; k<=numar_noduri; k++)//parcurgem toate nodurile
{
if(viz[k]==0)//daca gasim un nod nevizitat
{
stack<int> noduri;//stiva in care vom retine parcurgerea inversa a nodurilor in arborele dfs
dfs_stiva(k,viz,noduri);//functia ce ne returneaza prin parametru parcurgerea inversa
int numar_muchii2 = Graf_Orientat::get_nr_muchii();//retinem numarul de muchii pentru a nu apela functia get de prea multe ori
unordered_map<int,vector<int>> lista_ad;//lista_ad reprezinta listele de adiacenta pentru fiecare nod in graful transpus
for(int i=1; i<=numar_noduri; i++)//initializam lista_ad
{
if(viz[i]==1)
if(lista_adiacenta.find(i)!=lista_adiacenta.end())
for(int j=0; j<lista_adiacenta[i].size(); j++)
lista_ad[lista_adiacenta[i][j]].push_back(i);
}
Graf_Orientat g2(numar_noduri,numar_muchii2,lista_ad);//cream graful transpus
vector<int> viz2(numar_noduri+1,0);//vector ce retine daca un nod este sau nu vizitat
while(!noduri.empty())//cat timp stiva nu e goala
{
set<int,less<int>> componenta_tare_conexa;//in acest set vom retine componenta tare conexa curenta
if(viz2[noduri.top()]==0)//daca nodul din varf nu este vizitat
{
g2.dfs_tare_conex(noduri.top(),viz2,componenta_tare_conexa);//apelam dfs_tare_conex pe graful transpus incepand cu nodul din varf
if(componenta_tare_conexa.size()!=0)//daca componenta nu e goala, inseamna ca avem o solutie valida
{
componente_conexe.push_back(componenta_tare_conexa);//adaugam componenta tare conexa in solutie
componenta_tare_conexa.clear();//eliberam memoria din componenta_tare_conexa pentru a o refolosi
}
}
noduri.pop();//eliminam un nod din varf si reluam while-ul
}
}
}
return componente_conexe;
}
vector<int> Graf_Orientat::bfs(int nod_start)
{
int nr_noduri2 = Graf_Orientat::get_nr_noduri();//retinem numarul de noduri pentru a nu apela de fiecare data functia get
queue<int> bfs_queue;//coada in care vom adauga nodurile pe masura ce parcurgem graful
bfs_queue.push(nod_start);//adaugam in coada primul nod
vector<int> viz(nr_noduri2+1,0);//vectorul ce retine daca un nod a fost sau nu vizitat
viz[nod_start] = 1;//nod de start devine vizitat
vector<int> distanta(nr_noduri2+1,-1);//vectorul in care vom retine distanta de la nod_start la fiecare nod (este indexat de la 1)
distanta[nod_start]=0;//initalizam distanta de la nod_start la el insusi
while(!bfs_queue.empty())//cat timp coada nu e goala
{
int front_queue = bfs_queue.front();//retinem primul element din coada pentru a nu apela front de fiecare data
if(lista_adiacenta.find(front_queue)!=lista_adiacenta.end())
{
for(int i=0;i<lista_adiacenta[front_queue].size();i++)//parcurgem vecinii primului nod si verificam daca sunt vizitati
{
if(viz[lista_adiacenta[front_queue][i]]==0)//daca gasim un vecin nevizitat , il punem in coada, actualizam distanta lui cu distanta parintelui+1 si il notam ca vizitat
{
bfs_queue.push(lista_adiacenta[front_queue][i]);
distanta[lista_adiacenta[front_queue][i]]=distanta[front_queue]+1;
viz[lista_adiacenta[front_queue][i]]=1;
//cout<<"\n"<<front_queue<<" "<<lista_adiacenta[front_queue][i-1]<<" "<<contor;
}
}
}
bfs_queue.pop();//la final eliminam un nod din coada si se reia while-ul pana nu mai avem noduri
}
return distanta;
}
int Graf_Orientat::get_nr_muchii()
{
return this -> numar_muchii;
}
unordered_map<int,vector<int>> Graf_Orientat::get_lista_adiacenta()
{
return this -> lista_adiacenta;
}
Graf_Orientat::Graf_Orientat():Graf()
{
this -> numar_muchii = 0;
}
Graf_Orientat::Graf_Orientat(int nr_noduri,int numar_muchii,unordered_map <int,vector<int>> lista_adiacenta):Graf(nr_noduri)
{
this->numar_muchii = numar_muchii;
this->lista_adiacenta = lista_adiacenta;
}
Graf_Orientat::Graf_Orientat(const Graf_Orientat& g):Graf(g)
{
this -> numar_muchii = g.numar_muchii;
this -> lista_adiacenta= g.lista_adiacenta;
}
Graf_Orientat& Graf_Orientat::operator=(const Graf_Orientat& g)
{
if(this!= &g)
{
Graf::operator=(g);
this->numar_muchii = g.numar_muchii;
this->lista_adiacenta = g.lista_adiacenta;
}
*this;
}
ifstream& Graf_Orientat::citire_graf_virtuala_fisier(ifstream& in)
{
Graf::citire_graf_virtuala_fisier(in);
in>>this->numar_muchii;
for(int i=1;i<=this->numar_muchii;i++)
{
int first,second;
in>>first>>second;
int ok =1;
if(lista_adiacenta.find(first)!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[first].size();i++)
if(second==lista_adiacenta[first][i])
{
ok=0;
break;
}
if(ok==1)
lista_adiacenta[first].push_back(second);
}
return in;
}
ifstream& operator>>(ifstream& in,Graf_Orientat& g)
{
return g.citire_graf_virtuala_fisier(in);
}
Graf_Orientat::~Graf_Orientat(){}
int main()
{
//exercitiul DFS
/*ifstream fin("dfs.in");
ofstream fout("dfs.out");
Graf_Neorientat g;
fin>>g;
fout<<g.begin_dfs();*/
//exercitiul BFS
/*ifstream fin("bfs.in");
ofstream fout("bfs.out");
int nr_noduri,nr_muchii,nod_start;
unordered_map<int,vector<int>> lista_adiacenta;
fin>>nr_noduri>>nr_muchii>>nod_start;
for(int i=0;i<nr_muchii;i++)
{
int first,second;
fin>>first>>second;
lista_adiacenta[first].push_back(second);
}
Graf_Orientat g(nr_noduri,nr_muchii,lista_adiacenta);
vector<int> solutie;
solutie=g.bfs(nod_start);
for(int i=1;i<=nr_noduri;i++)
fout<<solutie[i]<<" ";*/
//exerctiul Biconexe
/*ifstream fin("biconex.in");
ofstream fout("biconex.out");
Graf_Neorientat g;
fin>>g;
vector<set<int,less<int>>> solutie;
solutie=g.begin_biconex();
fout<<solutie.size()<<"\n";
for(int i=0;i<solutie.size();i++)
{
for(auto itr=solutie[i].begin();itr!=solutie[i].end();itr++)
fout<<*itr<<" ";
fout<<"\n";
}*/
//exercitiul CTC
/*ifstream fin("ctc.in");
ofstream fout("ctc.out");
Graf_Orientat g;
fin>>g;
vector<set<int,less<int>>> solutie;
solutie = g.begin_componente_tare_conexe();
fout<<solutie.size()<<"\n";
for(int i=0; i<solutie.size(); i++)
{
for(auto itr=solutie[i].begin(); itr!=solutie[i].end(); itr++)
fout<<*itr<<" ";
fout<<"\n";
}*/
//exercitiul Sortaret
/*ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
Graf_Orientat g;
fin>>g;
vector<int> solutie;
solutie=g.begin_sortaret();
for(int i=0;i<solutie.size();i++)
fout<<solutie[i]<<" ";*/
//exercitiul havel hakimi
/*int n;
cout<<"Numarul de noduri =";
cin>>n;
vector<int> grade;
for(int i=0;i<n;i++)
{
int grad;
cout<<"Grad "<<i+1<<" =";
cin>>grad;
grade.push_back(grad);
}
sort(grade.begin(), grade.end(), greater<int>());
if(Graf_Neorientat::havel_hakimi(grade))
cout<<"da";
else
cout<<"nu";*/
//exercitiul muchie critica
/* int n,m;
cout<<"Numarul de noduri = ";
cin>>n;
cout<<"Numarul de muchii = ";
cin>>m;
vector<vector<int>> muchii;
for(int i=0;i<m;i++)
{
int prim,sec;
cout<<"Muchia "<<i+1<<" :";
cin>>prim>>sec;
vector<int> muchie_curenta;
muchie_curenta.push_back(prim);
muchie_curenta.push_back(sec);
muchii.push_back(muchie_curenta);
}
vector<vector<int>> sol=Graf_Neorientat::muchii_critice(n,muchii);
for(int i=0;i<sol.size();i++)
{
cout<<sol[i][0]<<" "<<sol[i][1]<<"\n";
}*/
//exercitiul APM
ifstream fin("apm.in");
ofstream fout("apm.out");
Graf_Neorientat_Cost g;
fin>>g;
vector<pair<int,int>> solutie;
int suma;
solutie = g.begin_APM(suma);
fout<<suma<<"\n";
fout<<solutie.size()<<"\n";
for(int i=0;i<solutie.size();i++)
fout<<solutie[i].first<<" "<<solutie[i].second<<"\n";
/*fout.close();
fin.close();*/
return 0;
}
Virgil Turcu Virgil993