Pagini recente » Cod sursa (job #154760) | Cod sursa (job #2386546) | Cod sursa (job #2476691) | Cod sursa (job #739660) | Cod sursa (job #408848)
Cod sursa(job #408848)
#include <stdio.h>
#include <fstream>
#define size 100010
#define min(a,b) a<b?a:b
using namespace std;
struct nod
{
int inf;
nod * next;
}*R[size],*G[size];
int viz[size];
int st[size];
int nr_rez,vf;
int low[size],niv[size];
int nr,n,m,x2,x1;
void add(nod *&a,int i)
{
nod *q=new nod;
q->inf=i;
q->next=a;
a=q;
}
void citire()
{
scanf ("%d %d",&n,&m);
for (int i=0;i<m;i++)
{
scanf ("%d %d",&x1,&x2);
add(G[x1],x2);
add(G[x2],x1);
}
}
void add_rez(int a,int b)
{
nr_rez++;
do
{
add(R[nr_rez],st[vf]);
add(R[nr_rez],st[vf-1]);
vf-=2;
}while (st[vf+2]!=b || st[vf+1]!=a);
}
void df(int Nod)
{
viz[Nod]=1;
low[Nod]=niv[Nod]=nr++;
for (nod *i=G[Nod];i;i=i->next)
if (!viz[i->inf])
{
st[++vf]=Nod;
st[++vf]=i->inf;
df(i->inf);
if (low[i->inf]>=niv[Nod])
add_rez(Nod,i->inf);
low[Nod]=min(low[i->inf],low[Nod]);
}
else
low[Nod]=min(niv[i->inf],low[Nod]);
}
void afish()
{
printf("%d\n",nr_rez);
for (int i=1;i<=nr_rez;i++)
{
memset(viz,0,sizeof(viz));
for (nod *j=R[i];j;j=j->next)
if (!viz[j->inf])
{
printf("%d ",j->inf);
viz[j->inf]=1;
}
printf("\n");
}
}
int main ()
{
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
citire();
for (int i=1;i<=n;i++)
if (!viz[i])
{
nr=1;
df(i);
}
afish();
return 0;
}