Pagini recente » Cod sursa (job #1649468) | Cod sursa (job #52463) | Cod sursa (job #873648) | Cod sursa (job #356632) | Cod sursa (job #572874)
Cod sursa(job #572874)
#include <cstdio>
#include <cstring>
#define MaxN 100002
#define infile "biconex.in"
#define outfile "biconex.out"
struct edge{
int x;
edge *next;
} *G[MaxN],*sol[MaxN];
int N,M,uz[MaxN],Nr,Q[MaxN*4],p,niv[MaxN],nivm[MaxN],t[MaxN];
void add(int x,int y)
{
edge *q=new edge;
q->x=y; q->next=G[x]; G[x]=q;
}
void read()
{
int x,y;
scanf("%d%d",&N,&M);
for(;M;M--)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
}
void update(int x,int y)
{
int xi,yi;
Nr++;
do{
xi=Q[p]; yi=Q[p];
edge *q=new edge;
q->x=xi; q->next=sol[Nr]; sol[Nr]=q;
q=new edge;
q->x=yi; q->next=sol[Nr]; sol[Nr]=q;
p-=2;
}while(xi!=y && yi!=x);
}
int minim(int x,int y)
{
if(x<y)
return x;
return y;
}
void dfs(int nod,int lev)
{
edge *q;
uz[nod]=1;
niv[nod]=nivm[nod]=lev;
for(q=G[nod];q;q=q->next)
if(q->x!=t[nod])
{
if(!uz[q->x])
{
Q[++p]=nod; Q[++p]=q->x;
t[q->x]=nod;
dfs(q->x,lev+1);
if(nivm[q->x]>=niv[nod])
update(nod,q->x);
nivm[nod]=minim(nivm[nod],nivm[q->x]);
}
else
nivm[nod]=minim(nivm[nod],niv[q->x]);
}
}
void solve()
{
int i;
for(i=1;i<=N;i++)
if(!uz[i])
dfs(i,1);
}
void write()
{
int i;
edge *q;
memset(uz,0,sizeof(uz));
printf("%d\n",Nr);
for(i=1;i<=Nr;i++)
{
for(q=sol[i];q;q=q->next)
uz[q->x]=0;
for(q=sol[i];q;q=q->next)
if(!uz[q->x])
{
printf("%d ",q->x);
uz[q->x]=1;
}
printf("\n");
}
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}