Pagini recente » Cod sursa (job #589218) | Cod sursa (job #2832994) | Cod sursa (job #192012) | Cod sursa (job #239950) | Cod sursa (job #2378421)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,k,num;
int v[100001];
int stk[200002][2];
struct mc{int d;mc*n;}*a[100001];
struct dmc{int a,b;dmc*n;};
struct vmc{vmc*n;dmc*m;}*K;
void dstk(int i,int j)
{
vmc*t=new vmc;t->m=NULL;t->n=K;K=t;
while(stk[k][0]!=i&&stk[k][1]!=j)
{
--k;
dmc*t2=new dmc;t2->n=t->m;t->m=t2;
t2->a=stk[k][0];
t2->b=stk[k][1];
}
++num;
}
int dfsl(int i,int ld,int o)
{
v[i]=ld;
for(mc*l=a[i];l!=NULL;l=l->n)
{
int j=l->d;
if(j!=o)
{
if(0==v[j])
{stk[k][0]=i;stk[k][1]=j;++k;
int ma=dfsl(j,v[i]+1,i);
if(ma<v[i])ld=min(ma,ld);
else
{
dstk(i,j);
}
}
else ld=min(ld,v[j]);
}
}
return ld;
}
int main()
{
f>>n>>m;K=NULL;
for(int i=1;i<=n;++i)a[i]=NULL;
for(int i=1;i<=m;++i){int x,y;f>>x>>y;
mc*l=new mc;l->d=x;l->n=a[y];a[y]=l;
l=new mc;l->d=y;l->n=a[x];a[x]=l;
}
for(int i=1;i<=n;++i)if(v[i]==0)dfsl(i,1,1);
for(int i=1;i<=n;++i)v[i]=0;
k=1;
g<<num<<'\n';
for(vmc*q=K;q!=NULL;q=q->n)
{
for(dmc*t=q->m;t!=NULL;t=t->n){if(v[t->a]!=k)
{v[t->a]=k;g<<t->a<<' ';}
if(v[t->b]!=k)
{v[t->b]=k;g<<t->b<<' ';}
}
g<<'\n';++k;
}
}