Pagini recente » Profil TudoseSanziana | Cod sursa (job #280178)
Cod sursa(job #280178)
//componente biconexe bc
#include <stdio.h>
#include <fstream.h>
#define nmax 100001
struct nod
{
int inf;
nod *urm;
} *g[nmax],*sol[nmax];
int n,m,st[4*nmax],vf,nr,nrsol;
int low[nmax],viz[nmax],niv[nmax];
int min(int x, int y)
{
return x<y?x:y;
}
void baga(int x, int y)
{
nod *q=new nod;
q->inf=y;
q->urm=g[x];
g[x]=q;
q=new nod;
q->inf=x;
q->urm=g[y];
g[y]=q;
}
void citire()
{
int x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
baga(x,y);
}
}
void update(int x, int y)
{
nrsol++;
int z1,z2;
do
{
z1=st[vf];
z2=st[vf-1];
nod *q=new nod;
q->inf=z1;
q->urm=sol[nrsol];
sol[nrsol]=q;
q=new nod;
q->inf=z2;
q->urm=sol[nrsol];
sol[nrsol]=q;
vf-=2;
}
while(z1-y || z2-x);
}
void parc(int x)
{
viz[x]=1;
low[x]=niv[x]=nr++;
for(nod *q=g[x];q;q=q->urm)
if(!viz[q->inf])
{
st[++vf]=x;
st[++vf]=q->inf;
parc(q->inf);
if(low[q->inf]>=niv[x])
update(x,q->inf);
low[x]=min(low[x],low[q->inf]);
}
else
low[x]=min(low[x],niv[q->inf]);
}
void solve()
{
for(int i=1;i<=m;i++)
if(!viz[i])
{
nr=1;
parc(i);
}
}
void afisare()
{
memset(viz,0,sizeof(viz));
printf("%d\n",nrsol);
for(int i=1;i<=nrsol;i++)
{
for (nod *p=sol[i];p;p=p->urm)
viz[p->inf]=0;
for(nod *q=sol[i];q;q=q->urm)
if (!viz[q->inf])
{
viz[q->inf]=1;
printf("%d ",q->inf);
}
printf("\n");
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}