Cod sursa(job #395128)

Utilizator irene_mFMI Irina Iancu irene_m Data 12 februarie 2010 10:30:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <cstdio>
#include <string>
#define MaxN 100240

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

int N,M,nr,uz[MaxN],df[MaxN],lev[MaxN],s[4*MaxN],L;

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

void read()
{
      int i,x,y;
      freopen("biconex.in","r",stdin);
      scanf("%d%d",&N,&M);
      for(i=1;i<=M;i++)
      {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
      }
}

void update(int x,int y)
{
      int xi,yi;
      nr++;
      do{
            xi=s[L]; yi=s[L-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;

            L-=2;

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

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

void dfs(int nod,int niv,int tt)
{
      edge *q;
      df[nod]=lev[nod]=niv;
      uz[nod]=1;

      for(q=G[nod];q!=NULL;q=q->next)
            if(q->x!=tt)
            {
                  if(!uz[q->x])
                  {
                        s[++L]=nod; s[++L]=q->x;
                        dfs(q->x,niv+1,nod);
                        if(lev[q->x]>=df[nod])
                              update(nod,q->x);

                        lev[nod]=minim(lev[nod],lev[q->x]);
                  }
                  else
                        lev[nod]=minim(lev[nod],df[q->x]);
            }

}

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

void write()
{
      int i;
      edge *q;
      freopen("biconex.out","w",stdout);
      printf("%d\n",nr);
      memset(uz,0,sizeof(uz));

      for(i=1;i<=nr;i++)
      {
            for(q=sol[i];q!=NULL;q=q->next)
                  uz[q->x]=0;

            for(q=sol[i];q!=NULL;q=q->next)
                  if(!uz[q->x])
                  {
                        uz[q->x]=1;
                        printf("%d ",q->x);
                  }
            printf("\n");
      }
}

int main()
{
      read();
      solve();
      write();
      return 0;
}