Cod sursa(job #272781)

Utilizator 630r63Ilinca George Mihai 630r63 Data 7 martie 2009 19:38:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream.h>
#define nmax (100005)
#define nmax2 (200005)

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;
}