Pagini recente » Cod sursa (job #3130813) | Cod sursa (job #1333279) | Cod sursa (job #1171348) | Cod sursa (job #3242280) | Cod sursa (job #2378419)
#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 vmc{vmc*n;mc*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;
mc*t2=new mc;t2->n=t->m;t->m=t2;
t2->d=stk[k][0];
t2=new mc;t2->n=t->m;t->m=t2;
t2->d=stk[k][1];
}
++num;
}
int dfsl(int i,int ld,int d,int o)
{
v[i]=d;
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,d+1,d+1,i);
if(ma<ld)ld=ma;
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;
}
dfsl(1,1,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(mc*t=q->m;t!=NULL;t=t->n)if(v[t->d]!=k)
{v[t->d]=k;g<<t->d<<' ';}
g<<'\n';++k;
}
}