Cod sursa(job #372974)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 12 decembrie 2009 12:38:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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,MU[NM][2],cate,L[NM],HM[NM],bicomp;

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

char U[NM];

void parc(int nod,int fat)
{
     L[nod]=L[fat]+1;
     HM[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);
         
         HM[nod]=min(HM[nod],HM[nnod]);
         
         if(HM[nnod]>=L[nod])
         {
           //trebuie eliberata stiva
           
           ++bicomp;
       
           while(MU[cate][0]!=nod)
           {
             BI[bicomp].PB(MU[cate][1]);
             --cate;
           }
       
           BI[bicomp].PB(MU[cate][1]); 
           BI[bicomp].PB(MU[cate][0]);
           
           --cate;
         }
       }
       else HM[nod]=min(HM[nod],L[nnod]);
     }
}

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