Pagini recente » Cod sursa (job #2024545) | Cod sursa (job #3281792) | Cod sursa (job #1998445) | Cod sursa (job #239620) | Cod sursa (job #269920)
Cod sursa(job #269920)
#include <fstream.h>
#define nmax (10005)
#define nmax2 (20005)
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct lista {long nod; lista *urm;};
struct l2{long x, y; l2 *urm,*prec;};
long n,m,t[nmax],l[nmax],nv[nmax],nr;
lista *a[nmax2];
l2 *s, *sol[nmax2];
void add(long x, long y)
{lista *p;
p=new lista;
p->nod=y;
p->urm=0;
if (a[x])
p->urm=a[x];
a[x]=p;
}
void pushsol(long x, long y)
{l2 *d;
d=new l2;
d->x=x;
d->y=y;
d->urm=0;
d->prec=0;
if(sol[nr]!=0)
{d->prec=sol[nr];
sol[nr]->urm=d;
}
sol[nr]=d;
}
void pop(long *x, long *y)
{l2 *d;
d=new l2;
*x=s->x;
*y=s->y;
d=s;
s=s->prec;
delete d;
}
void push(long x, long y)
{l2 *d;
d=new l2;
d->x=x;
d->y=y;
d->urm=0;
d->prec=0;
if(s!=0)
{d->prec=s;
s->urm=d;
}
s=d;
}
void df(long k)
{lista *p;
l2 *d;
long x,y;
l[k]=nv[k];
for (p=a[k];p!=0;p=p->urm)
if (!t[p->nod])
{push(k,p->nod);
t[p->nod]=k;
nv[p->nod]=nv[k]+1;
df(p->nod);
if (l[p->nod]<l[k]) l[k]=l[p->nod];
if (l[p->nod]>=nv[k])
{nr++;
do
{pop(&x,&y);
pushsol(x,y);
}
while (s && (x!=k || y!=p->nod) && (x!=p->nod || y!=k));
}
}
else
if (p->nod!=t[k] && nv[p->nod]<l[k])
l[k]=nv[p->nod];
}
int main()
{long i,p1,p2,x,y;
fin>>n>>m;
for (i=1;i<=m;i++)
{fin>>p1>>p2;
add(p1,p2);
add(p2,p1);
}
for (i=1;i<=n;i++)
if (!t[i])
{t[i]=-1;
nv[i]=1;
df(i);
}
fout<<nr<<'\n';
memset(t,0,sizeof(t));
for (i=1;i<=nr;i++)
{
do
{y=sol[i]->y;
x=sol[i]->x;
if (t[x]!=i)
{fout<<x<<" ";
t[x]=i;
}
if (t[y]!=i)
{fout<<y<<" ";
t[y]=i;
}
sol[i]=sol[i]->prec;
}
while (sol[i]);
fout<<'\n';
}
fout.close();
return 0;
}