Cod sursa(job #572856)

Utilizator irene_mFMI Irina Iancu irene_m Data 5 aprilie 2011 18:07:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
#include <cstdio>
#include <cstring>
#define MaxN 100002
#define infile "biconex.in"
#define outfile "biconex.out"

struct edge{
      int x;
      edge *next;
} *G[MaxN],*sol[MaxN];

int N,M,uz[MaxN],Nr,Q[MaxN*4],p,niv[MaxN],nivm[MaxN],t[MaxN];

void add(int x,int y)
{
      edge *q=new edge;
      q->x=y; q->next=G[x]; G[x]=q;
}

void read()
{
      int x,y;
      scanf("%d%d",&N,&M);
      for(;M;M--)
      {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
      }
}

void update(int x,int y)
{
      int xi,yi;
      Nr++;

      do{
            xi=Q[p]; yi=Q[p-1];

            edge *q=new edge;
            q->x=xi; q->next=sol[Nr]; sol[Nr]=q;

            q=new edge;
            q->x=yi; q->next=sol[Nr]; sol[Nr]=q;

            p-=2;
      }while(xi!=y || yi!=x);
}

int minim(int x,int y)
{
      if(x<y) return x;
      return y;
}

void dfs(int nod,int lev)
{
      edge *q;

      uz[nod]=1;
      niv[nod]=nivm[nod]=lev;

      for(q=G[nod];q;q=q->next)
            if(q->x!=t[nod])
            {
                  if(!uz[q->x])
                  {
                        Q[++p]=nod; Q[++p]=q->x;
                        t[q->x]=nod;
                        dfs(q->x,lev+1);
                        if(nivm[q->x]>=niv[nod])
                              update(nod,q->x);
                        nivm[nod]=minim(nivm[q->x],nivm[nod]);
                  }
                  else
                        nivm[nod]=minim(nivm[nod],niv[q->x]);
            }
}

void solve()
{
      int i;
      for(i=1;i<=N;i++)
            if(!uz[i])
                  dfs(i,1);
}

void write()
{
      int i;
      edge *q;
      printf("%d\n",Nr);
      memset(uz,0,sizeof(uz));
      for(i=1;i<=Nr;i++)
      {
            for(q=sol[i];q;q=q->next)
                  uz[q->x]=0;
            for(q=sol[i];q;q=q->next)
                  if(!uz[q->x])
                  {
                        printf("%d ",q->x);
                        uz[q->x]=1;
                  }
            printf("\n");
      }
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      solve();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}