Pagini recente » Cod sursa (job #1880611) | Cod sursa (job #475335) | Cod sursa (job #522887) | Cod sursa (job #919267) | Cod sursa (job #300813)
Cod sursa(job #300813)
#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,n0;
int sol[dim],v[dim],u[dim];
stiva *end;
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))
{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;
int x,y;
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;
list *q;
fin>>n>>m;
for (i=1;i<=m;i++)
{fin>>x>>y; add(x,y); add(y,x);}
for (i=1;i<=n;i++)
if (!t[i])
{nv[i]=1;
t[i]=-1;
dfs(i);
}
fout<<nr<<'\n';
i=1;
while(i<=n0)
{fout<<sol[i]<<" ";
for(i++;v[i]==v[i-1] && i<=n0;i++)
fout<<sol[i]<<" ";
fout<<'\n';
}
fout.close();
return 0;
}