Pagini recente » Cod sursa (job #3219596) | Cod sursa (job #3229989) | Cod sursa (job #3283387) | Istoria paginii utilizator/cojocaru_andrei_cristian | Cod sursa (job #280136)
Cod sursa(job #280136)
//componente biconexe bc
#include <stdio.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],tata[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 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])
{
tata[q->inf]=x;
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]);
}
int main()
{
int i,x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
baga(x,y);
}
for(i=1;i<=m;i++)
if(!viz[i])
{
nr=1;
parc(i);
}
printf("%d\n",nrsol);
for(i=1;i<=nrsol;i++)
{
for(nod *q=sol[i];q;q=q->urm)
viz[q->inf]=0;
for(q=sol[i];q;q=q->urm)
if(!viz[q->inf])
{
printf("%d ",q->inf);
viz[q->inf]=1;
}
printf("\n");
}
fclose(stdout);
return 0;
}