Cod sursa(job #372875)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 11 decembrie 2009 22:09:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define NM 100005
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)
#define PB push_back

int N,M,L[NM],MU[NM][2],cate,LOW[NM],bicomp;

vector <int> G[NM],BI[NM];

char U[NM];

void parc(int nod,int fat)
{
     L[nod]=L[fat]+1;
     LOW[nod]=L[nod];
     U[nod]=1;
     
     FOR(i,0,G[nod].size()-1)
     {
       int nnod=G[nod][i];
       
       if(nnod==fat) continue;
       
       if(!U[nnod])
       {
         ++cate;
         MU[cate][0]=nod;
         MU[cate][1]=nnod;
         
         parc(nnod,nod);
       }
       
       LOW[nod]=min(LOW[nod],LOW[nnod]);
     }
     
     if(LOW[nod]==L[nod])
     {
       //trebuie sa scoti din stiva
       
       ++bicomp;
       
       while(MU[cate][1]!=nod)
       {
         BI[bicomp].PB(MU[cate][1]);
         --cate;
       }
       
       BI[bicomp].PB(nod);
       
       if(BI[bicomp].size()==1)
       {
         BI[bicomp].clear();
         --bicomp;
       }
       
       if(fat)
       {
         ++bicomp;
       
         BI[bicomp].PB(nod);
         BI[bicomp].PB(fat);
         
         --cate;
       }  
     }
     
}

int main()
{
    int a,b;
    
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    
    scanf("%d %d",&N,&M);
    
    FOR(i,1,M)
    {
      scanf("%d %d",&a,&b);
      
      G[a].PB(b);
      G[b].PB(a);
    }
    
    L[0]=0;
    
    ++cate;
    MU[1][0]=0;
    
    FOR(i,1,N)
      if(!U[i])
      {
        MU[1][1]=i;
        parc(i,0);
      }  
    
    printf("%d\n",bicomp);
    
    FOR(i,1,bicomp)
    {
      FOR(j,0,BI[i].size()-1)
        printf("%d ",BI[i][j]);             
                   
      printf("\n");
    }
    
    return 0;
}