Pagini recente » Cod sursa (job #2335185) | Cod sursa (job #863760) | Cod sursa (job #1364774) | Cod sursa (job #222702) | Cod sursa (job #2784258)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconexe.in");
ofstream fout("biconexe.out");
struct muchie
{
int x,y;
muchie(int a, int b)
{
x=a;
y=b;
}
muchie(){}
};
int vizitat[100005];
int moment[100005]; //vector ce retine momentul in care se viziteaza prima oara un nod di graf
int low[100005]; //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
vector<set<int>> biconexe; //vectorul de componente biconexe
int n, m,timp=0; // start contor de timp pentru crearea vectorului moment
//liste de adiacente
vector<vector<int>> la;
//subprogram de determinare a componentelor biconexe
void bcx(int curent, int fiu)
{
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!=curent || b!=fiu);
biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
}
//parcurgere dfs
void dfs(int x, int y) //x = nodul curent, y = parintele sau
{
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(z, x);
//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
bcx(x, z);
}
else //am dat de o muchie de intoarcere
{
if(z!=y) //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];
}
}
}
}
int main()
{
fin>>n>>m;
la.resize(n+1);
for(int i=0; i<m; ++i)
{
int x ,y;
fin >> x >> y;
la[x].push_back(y);
la[y].push_back(x);
}
dfs(1, 0);
fout << biconexe.size() << "\n";
for(int i=0; i<biconexe.size(); ++i)
{
for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
fout << *it << " ";
fout << "\n";
}
}