#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);
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();
virtual string tip_graf();
virtual int begin_dfs();
void dfs(int nod, int viz[]);
virtual void bfs(int nod_start);
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::bfs(int nod_start)
{
int viz[Graf::get_nr_noduri()+1]={0};
ofstream fout("bfs.out");
int contor = 0;
int distanta[Graf::get_nr_noduri()+1]={-1};
queue<int> bfs_queue;
bfs_queue.push(nod_start);
viz[nod_start] = 1;
while(!bfs_queue.empty())
{
contor++;
int front_queue = bfs_queue.front();
if(lista_adiacenta.find(front_queue)!=lista_adiacenta.end())
{
for(int i=1;i<=lista_adiacenta[front_queue].size();i++)
{
if(viz[lista_adiacenta[front_queue][i-1]]==0)
{
bfs_queue.push(lista_adiacenta[front_queue][i-1]);
distanta[lista_adiacenta[front_queue][i-1]]=contor;
viz[lista_adiacenta[front_queue][i-1]]=1;
}
}
}
bfs_queue.pop();
}
distanta[nod_start] = 0;
for(int i=1;i<=Graf::get_nr_noduri();i++)
fout<<distanta[i]<<" ";
}
void Graf_Neorientat::dfs(int nod,int viz[])
{
viz[nod] = 1;
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
{
for(int i=1;i<=lista_adiacenta[nod].size();i++)
if(viz[lista_adiacenta[nod][i-1]]==0)
dfs(lista_adiacenta[nod][i-1],viz);
}
}
int Graf_Neorientat::begin_dfs()
{
int viz[Graf::get_nr_noduri()+1] ={0};
int contor=0;
for(int i=1;i<=Graf::get_nr_noduri();i++)
if(viz[i]==0)
{
contor++;
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_Orientat:public Graf
{
private:
int numar_muchii;
unordered_map<int,vector<int>>lista_adiacenta;
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();
//functie virtuala pura
string tip_graf();
int begin_dfs();
void dfs(int nod, int viz[]);
void bfs(int nod_start);
void dfs_stiva(int nod,int viz[],stack<int> &noduri);
void dfs_tare_conex(int nod,int viz[],set<int,less<int>> &componenta_tare_conexa);
void begin_componente_tare_conexe();
void 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";
}
void Graf_Orientat::begin_sortaret()
{
int numar_noduri = Graf_Orientat::get_nr_noduri();
int grad_interior[numar_noduri+1]={0};
int viz[numar_noduri+1] = {0};
for(int i=1;i<=numar_noduri;i++)
{
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;
for(int i=1;i<=numar_noduri;i++)
if(grad_interior[i]==0)
{
coada_noduri.push(i);
viz[i] = 1;
}
ofstream fout4("sortaret.out");
while(!coada_noduri.empty())
{
fout4<<coada_noduri.front()<<" ";
if(lista_adiacenta.find(coada_noduri.front())!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[coada_noduri.front()].size();i++)
{
grad_interior[lista_adiacenta[coada_noduri.front()][i]]--;
if(grad_interior[lista_adiacenta[coada_noduri.front()][i]]==0)
{
viz[lista_adiacenta[coada_noduri.front()][i]]=1;
coada_noduri.push(lista_adiacenta[coada_noduri.front()][i]);
}
}
coada_noduri.pop();
}
}
void Graf_Orientat::dfs_stiva(int nod,int viz[],stack<int> &noduri)
{
viz[nod] = 1;
int numar_noduri = Graf_Orientat::get_nr_noduri();
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[nod].size();i++)
{
if(viz[lista_adiacenta[nod][i]]==0)
dfs_stiva(lista_adiacenta[nod][i],viz,noduri);
}
noduri.push(nod);
}
void Graf_Orientat::dfs_tare_conex(int nod,int viz[],set<int,less<int>> &componenta_tare_conexa)
{
viz[nod]=1;
componenta_tare_conexa.insert(nod);
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
for(int i=0;i<lista_adiacenta[nod].size();i++)
{
if(viz[lista_adiacenta[nod][i]]==0)
dfs_tare_conex(lista_adiacenta[nod][i],viz,componenta_tare_conexa);
}
}
void Graf_Orientat::begin_componente_tare_conexe()
{
int numar_noduri = Graf_Orientat::get_nr_noduri();
int viz[numar_noduri+1]= {0};
int nr_componente_tare_conexe=0;
ofstream fout2("ctc.out");
vector<set<int,less<int>>> componente_conexe;
for(int k=1; k<=numar_noduri; k++)
{
if(viz[k]==0)
{
stack<int> noduri;
dfs_stiva(k,viz,noduri);
int numar_muchii2 = Graf_Orientat::get_nr_muchii();
unordered_map<int,vector<int>> lista_ad;
for(int i=1; i<=numar_noduri; i++)
{
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);
int viz2[numar_noduri+1]= {0};
stack<int> noduri_copy=noduri;
while(!noduri_copy.empty())
{
set<int,less<int>> componenta_tare_conexa;
if(viz2[noduri_copy.top()]==0)
{
g2.dfs_tare_conex(noduri_copy.top(),viz2,componenta_tare_conexa);
if(componenta_tare_conexa.size()!=0)
{
componente_conexe.push_back(componenta_tare_conexa);
componenta_tare_conexa.clear();
}
}
noduri_copy.pop();
}
}
}
fout2<<componente_conexe.size()<<"\n";
for(int i=0;i<componente_conexe.size();i++)
{
for(auto itr=componente_conexe[i].begin();itr!=componente_conexe[i].end();itr++)
fout2<<*itr<<" ";
fout2<<"\n";
}
}
void Graf_Orientat::bfs(int nod_start)
{
int viz[Graf::get_nr_noduri()+1]={0};
ofstream fout("bfs.out");
int contor = 1;
int distanta[Graf::get_nr_noduri()+1];
for(int i=1;i<=Graf::get_nr_noduri();i++)
distanta[i]=-1;
queue<int> bfs_queue;
bfs_queue.push(nod_start);
viz[nod_start] = 1;
distanta[nod_start]=0;
while(!bfs_queue.empty())
{
int front_queue = bfs_queue.front();
if(lista_adiacenta.find(front_queue)!=lista_adiacenta.end())
{
for(int i=1;i<=lista_adiacenta[front_queue].size();i++)
{
if(viz[lista_adiacenta[front_queue][i-1]]==0)
{
bfs_queue.push(lista_adiacenta[front_queue][i-1]);
distanta[lista_adiacenta[front_queue][i-1]]=distanta[front_queue]+1;
viz[lista_adiacenta[front_queue][i-1]]=1;
cout<<"\n"<<front_queue<<" "<<lista_adiacenta[front_queue][i-1]<<" "<<contor;
}
}
}
bfs_queue.pop();
}
distanta[nod_start] = 0;
for(int i=1;i<=Graf::get_nr_noduri();i++)
fout<<distanta[i]<<" ";
}
void Graf_Orientat::dfs(int nod,int viz[])
{
viz[nod] = 1;
if(lista_adiacenta.find(nod)!=lista_adiacenta.end())
{
for(int i=1;i<=lista_adiacenta[nod].size();i++)
if(viz[lista_adiacenta[nod][i-1]]==0)
dfs(lista_adiacenta[nod][i-1],viz);
}
}
int Graf_Orientat::begin_dfs()
{
int viz[Graf::get_nr_noduri()+1] ={0};
int contor=0;
for(int i=1;i<=Graf::get_nr_noduri();i++)
if(viz[i]==0)
{
contor++;
Graf_Orientat::dfs(i,viz);
}
return contor;
}
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);
g.bfs(nod_start);*/
//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");
Graf_Orientat g;
fin>>g;
g.begin_componente_tare_conexe();*/
//exercitiul Sortaret
/*ifstream fin("sortaret.in");
Graf_Orientat g;
fin>>g;
g.begin_sortaret();*/
//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";
}*/
fout.close();
fin.close();
return 0;
}
Virgil Turcu Virgil993