Pagini recente » Cod sursa (job #2057726) | Cod sursa (job #30624) | Cod sursa (job #178035) | Cod sursa (job #2632552) | Cod sursa (job #395117)
Cod sursa(job #395117)
#include <cstdio>
#define MaxN 100240
struct edge{
int x;
edge *next;
} *G[MaxN],*sol[MaxN];
int N,M,nr,uz[MaxN],df[MaxN],lev[MaxN],s[MaxN],L;
void add(int x,int y)
{
edge *q=new edge;
q->x=y; q->next=G[x]; G[x]=q;
}
void read()
{
int i,x,y;
freopen("biconex.in","r",stdin);
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
}
void update(int x,int y)
{
int xi,yi;
edge *q;
nr++;
do{
xi=s[L]; yi=s[L-1];
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;
L-=2;
}while(xi!=y || yi!=x);
}
int minim(int x,int y)
{
if(x<y)
return x;
return y;
}
void dfs(int nod,int niv,int tt)
{
edge *q;
df[nod]=lev[nod]=niv;
uz[nod]=1;
for(q=G[nod];q!=NULL;q=q->next)
if(q->x!=tt)
{
if(!uz[q->x])
{
s[++L]=nod; s[++L]=q->x;
dfs(q->x,niv+1,nod);
if(lev[q->x]>=df[nod])
update(nod,q->x);
lev[nod]=minim(lev[nod],lev[q->x]);
}
else
lev[nod]=minim(lev[nod],df[q->x]);
}
}
void solve()
{
int i;
for(i=1;i<=N;i++)
if(!uz[i])
dfs(i,1,0);
}
void write()
{
int i;
edge *q;
freopen("biconex.out","w",stdout);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
for(q=sol[i];q!=NULL;q=q->next)
uz[q->x]=0;
for(q=sol[i];q!=NULL;q=q->next)
if(!uz[q->x])
{
uz[q->x]=1;
printf("%d ",q->x);
}
printf("\n");
}
}
int main()
{
read();
solve();
write();
return 0;
}