Pagini recente » Cod sursa (job #3201458) | Cod sursa (job #2673773) | Cod sursa (job #522770) | Cod sursa (job #2602112) | Cod sursa (job #2310922)
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[200005],afis[200005];
int n,m,a,b,lv[200005],stramos[200005],viz[200005],tata[200005],t,r,j;
const int inf=20000000;
struct vct
{
int x,y;
}muchie[200005];
///lv= nivelul nodului in arbore
///stramos= cel mai mic nivel la care poate urca un nod folosind o muchie de intoarcere
///muchie= gen stiva cu muchii in ordinea parcurgerii DFS
void componenta(int x, int y)
{///se elimina toate muchiile din stiva pana la muchia critica inclusiv
///muchiile eliminate formeaza o componenta biconexa
r++;
while(muchie[t].y!=y)
{
afis[r].push_back(muchie[t].x);
t--;
}
afis[r].push_back(muchie[t].x);
afis[r].push_back(muchie[t].y);
t--;
}
void dfs(int start, int vecin, int bk)
{
int i;
viz[start]=1; lv[start]=lv[bk]+1; tata[start]=bk;
muchie[++t].x=start; muchie[t].y=bk;
for(i=0;i<v[start].size();i++)
{
vecin=v[start][i];
if(!viz[vecin])
{
dfs(vecin,0,start);
if(stramos[start]>stramos[vecin])
stramos[start]=stramos[vecin];///tata nu poate avea stramos mai mare decat fii
if(stramos[vecin]>=lv[start])
componenta(vecin,start);///am gasit fiu care nu poate urca mai sus decat tata
///(tata aici e nod de articulatie, iar muchia start-vecin e critica)
}
else
if(stramos[start]>lv[vecin] && vecin!=bk)
stramos[start]=lv[vecin];
}
}
int main()
{
ifstream f("componentebiconexe.in");
ofstream g("componentebiconexe.out");
int i;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
for(i=1;i<=n;i++)
stramos[i]=inf;
dfs(1,0,0);
g<<r<<'\n';
for(i=1;i<=r;i++)
{
for(j=0;j<afis[i].size();j++)
g<<afis[i][j]<<' ';
g<<'\n';
}
return 0;
}