Pagini recente » Cod sursa (job #2975057) | Cod sursa (job #1646682) | Cod sursa (job #312457) | Cod sursa (job #561500) | Cod sursa (job #300863)
Cod sursa(job #300863)
#include <fstream.h>
#define dim 100005
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct list{int nod; list *urm;};
struct stiva{int x,y; stiva *urm,*pred;};
list *L[dim];
int nv[dim], l[dim], t[dim];
int n,nr;
int sol[2*dim],v[2*dim],u[dim];
stiva *end;
int n0;
void add(int x, int y)
{list *p=new list;
p->nod=y;
p->urm=L[x];
L[x]=p;
}
void push(int x, int y)
{stiva *q=new stiva;
q->x=x;
q->y=y;
q->urm=0;
q->pred=end;
end=q;
}
void pop(int *x, int *y)
{stiva *d;
d=end;
*x=end->x;
*y=end->y;
end=end->pred;
delete d;
}
void comp_noua(int S, int F)
{int x,y;
nr++;
pop (&x, &y);
n0++; sol[n0]=x; v[n0]=nr;
n0++; sol[n0]=y; v[n0]=nr;
u[x]=nr; u[y]=nr;
while ((x!=F || y!=S) && (y!=F || x!=S))
{pop (&x, &y);
if (u[x]!=nr)
{ n0++; u[x]=nr;
sol[n0]=x;
v[n0]=nr;
}
if (u[y]!=nr)
{ n0++; u[y]=nr;
sol[n0]=y;
v[n0]=nr;
}
}
}
void dfs(int k)
{list *p;
l[k]=nv[k];
for (p=L[k];p;p=p->urm)
{if (p->nod!=t[k] && nv[k]>nv[p->nod])
push(p->nod,k);
if(!t[p->nod])
{nv[p->nod]=nv[k]+1;
t[p->nod]=k;
dfs(p->nod);
if (l[k]>l[p->nod]) l[k]=l[p->nod];
if (l[p->nod]>=nv[k])
comp_noua(k,p->nod);
}
else //am mai trecut prin el
if (p->nod!=t[k] && nv[p->nod]<l[k])
l[k]=nv[p->nod];
}
}
int main()
{int i,x,y,m;
fin>>n>>m;
for (i=1;i<=m;i++)
{fin>>x>>y; add(x,y); add(y,x);}
nr=0;
nv[1]=1;
dfs(1);
fout<<nr<<'\n';
i=1;
for (n0=1;n0<=nr;n0++)
{for(;v[i]==n0;i++)
fout<<sol[i]<<" ";
fout<<'\n';
}
fout.close();
return 0;
}