Pagini recente » Cod sursa (job #2976054) | Cod sursa (job #1064933) | Cod sursa (job #1673513) | Cod sursa (job #1755539) | Cod sursa (job #2149225)
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define nmax 100005
#define mmax 200005
int vf,nrf,nr,nrb,pas,cer,n,m,nro[nmax],low[nmax],art[nmax],t[nmax];
struct nod {int x,y;nod *urm;}*a[nmax],*b[nmax],*p;
struct stiva {int x,y;}c[mmax],mm[mmax];
void adaugare (nod*& p,int x) {
nod *q=new nod;
q->x=x;
q->urm=NULL;
if (p==NULL)
p=q;
else {
nod *nn=p;
while (nn->urm!=NULL)
nn=nn->urm;
nn->urm=q;}}
void read () {
c[1].x=1;
c[1].y=-1;
f>>n>>m;
int x,y;
for (int i=1;i<=m;++i) {
f>>x>>y;
adaugare(a[x],y);
adaugare(a[y],x);}
for (int i=1;i<=n;++i)
nro[i]=low[i]=-1;}
void muta (int fiu,int x) {
++nrb;
do {
nod *z=new nod;
z->x=c[vf].x;
z->y=c[vf].y;
z->urm=b[nrb];
b[nrb]=z;
--vf;
}while( !((c[vf+1].y==x && c[vf+1].x==fiu)||(c[vf+1].y==fiu && c[vf+1].x==x)));}
void biconex (int x) {
nod *q;
int fiu;
low[x]=nro[x]=++pas;
for (q=a[x];q;q=q->urm) {
fiu=q->x;
if (fiu!=t[x] && nro[fiu]<nro[x])
c[++vf].x=fiu,c[vf].y=x;
if (nro[fiu]==-1) {
if (x==1)
++nrf;
nro[fiu]=nro[x]+1;
t[fiu]=x;
biconex(fiu);
low[x]=min(low[x],low[fiu]);
if (low[fiu]>=nro[x]) {
if (x!=1)
art[x]=1;
muta(fiu,x);}
}
else if (fiu!=t[x])
low[x]=min(nro[fiu], low[x]);}}
void out1 (nod *p, int i) {
if (p) {
if(t[p->x]==0)
++nr;
if(t[p->y]==0)
++nr;
t[p->x]=i;
t[p->y]=i;
out1(p->urm,i);}}
int main()
{ read();
nro[1]=1;
biconex(1);
g<<nrb<<'\n';
for (int i=1;i<=nrb;++i) {
nr=0;
for(int j=1;j<=n;++j)
t[j]=0;
out1(b[i],i);
for(int j=1;j<=n;++j)
if(t[j]==i)
g<<j<<' ';
g<<'\n';}
return 0;
}