Pagini recente » Cod sursa (job #1907300) | Cod sursa (job #2244811) | Cod sursa (job #1334761) | Cod sursa (job #1995796) | Cod sursa (job #276946)
Cod sursa(job #276946)
#include <cstdio>
struct nod {int inf; nod *urm;} *g[100001],*sol[200001];
int st[200001],niv[100001],low[100001],tata[100001];
int viz[100001],vf;
int n,m,nr,nrsol;
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 i,int j)
{
int z1,z2;
nrsol++;
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-j || z2-i);
}
void dfs(int x)
{
viz[x]=1;
niv[x]=low[x]=nr++;
for(nod *i=g[x];i;i=i->urm)
{
if(!viz[i->inf])
{
tata[i->inf]=x;
st[++vf]=x;
st[++vf]=i->inf;
dfs(i->inf);
if(low[i->inf]>=niv[x])
update(x,i->inf);
low[x]=min(low[x],low[i->inf]);
}
else if(tata[x]!=i->inf)
low[x]=min(low[x],niv[i->inf]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
baga(x,y);
}
for(int i=1;i<=n;i++)
if(!viz[i])
{
nr=1;
dfs(i);
}
printf("%d\n",nrsol);
for(int i=1;i<=nrsol;i++)
{
for(nod *q=sol[i];q;q=q->urm)
viz[q->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");
}
}