Pagini recente » Istoria paginii runda/dv/clasament | Cod sursa (job #2008786) | Istoria paginii runda/pixelcup/clasament | Istoria paginii runda/12344321 | Cod sursa (job #2795840)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
class graf_neorientat
{
int n, m; //n = nr. noduri m = nr. muchii
public:
vector <int> lista[100005]; //in acest mod va fi stocat graful
stack <int> stiva;
int niv[100005], niv_ma[100005], numar_cb = 0;
vector <int> rezultat[100005];
graf_neorientat(int, int);
void construire_graf_neorientat();
void dfs_comp_biconexe(int, int, int);
int comp_biconexe(int, int);
};
graf_neorientat::graf_neorientat(int n, int m)
{
this -> n = n;
this -> m = m;
}
void graf_neorientat :: construire_graf_neorientat()
{
for(int i = 0; i < m; i ++) //parcurgem muchiile
{
int u, v;
in >> u >> v; //citim nodurile intre care exista muchie
lista[u].push_back(v);
//marcam in lista de 2 ori, fiind neorientat
lista[v].push_back(u);
}
}
int graf_neorientat :: comp_biconexe(int nod, int i)
{
numar_cb ++; //numara comp. biconexe
//elim. din stiva toate nodurile pana la i inclusiv si le punem in vectorul rezultat
//eliminarea nu se face pana la nod deoarece intre i si nod mai pot exista noduri care apartin altei comp. biconexe
while(stiva.top() != i)
{
rezultat[numar_cb].push_back(stiva.top());
stiva.pop();
}
rezultat[numar_cb].push_back(nod);
rezultat[numar_cb].push_back(i);
stiva.pop();
}
void graf_neorientat :: dfs_comp_biconexe(int nod, int nivel, int tata) //nod = nodul curent; nivel = niv. nodului; tata = tatal lui nod
{
niv_ma[nod] = nivel; //niv_ma[nod] = nivelul minim accesibil la care se poate ajunge din nod, mergand pe muchii de arbore, ultima muchie = de intoarcere
niv[nod] = nivel; //niv[nod] = nivelul nodului nod
stiva.push(nod); //in stiva se pun nodurile in ordinea parcurgerii in dfs
for(auto i : lista[nod]) //pentru fiecare nod din lista de adiacenta a nodului curent
{
if(!niv[i]) //daca nu a fost vizitat
{
dfs_comp_biconexe(i ,nivel + 1, nod); //apelare recursiva pentru fiecare nod i adiacent cu nodul curent
niv_ma[nod] = min(niv_ma[i], niv_ma[nod]); //calculeaza nivelul minim accesibil al nodului curent
if(niv_ma[i] >= nivel) //am gasit punct de articulatie
comp_biconexe(nod, i); //construieste componenta biconexa
//------------------------------------------
/*if(niv[nod] <= niv_ma[i] && niv[nod] != 1)
out << nod << " " << "este punct de articulatie" << endl;
//------------------------------------------
if(niv[nod] < niv_ma[i]) //afisarea muchiilor critice(critical connection)
{
muchii_critice.push_back(make_pair(nod, i));
}*/
}
else if(i != tata) //daca nodul a fost viz. dar e diferit de tatal lui nod => (nod, i) = muchie de intoarcere
niv_ma[nod] = min(niv_ma[nod], niv[i]); //actualizam nivelul minim accesibil al lui nod
}
}
int main()
{
int n, m;
in >> n >> m; //se citesc nr. de noduri, nr. de muchii
graf_neorientat G(n, m);
G.construire_graf_neorientat();
for(int i = 1; i <= n; i ++)
if(!G.niv[i]) //pentru fiecare nod nevizitat
G.dfs_comp_biconexe(i,1,0);
/*out << "Muchii crtice : " << endl;
for (int i = 0; i < G.muchii_critice.size(); i ++)
{
out << G.muchii_critice[i].first << " "
<< G.muchii_critice[i].second << endl;
}*/
out << "Nr. comp biconexe: " << G.numar_cb << '\n';
out << "Comp. biconexe: " << endl;
for(int i = 1; i <= G.numar_cb; i ++,cout << '\n')
for(auto j : G.rezultat[i])
out << j << " ";
}