Cod sursa(job #373307)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 13 decembrie 2009 14:57:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<iostream>
#include<string>
#include<vector>

using namespace std;

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

vector<int> G[NM],BI[NM];
int N,M;
int STK[NM][2],stk,L[NM],HM[NM],bi;
char U[NM];

void parc(int nod,int fat)
{
     HM[nod]=L[nod]=L[fat]+1;
     
     U[nod]=1;
     
     FOR(i,0,G[nod].size()-1)
     {
       int nnod=G[nod][i];
       
       if(nnod==fat) continue;
       
       if(!U[nnod])
       {
         ++stk;
         
         STK[stk][0]=nod;
         STK[stk][1]=nnod;          
                   
         parc(nnod,nod);
         
         HM[nod]=min(HM[nod],HM[nnod]);
         
         if(HM[nnod]>=L[nod])
         {
           ++bi;
           
           while(STK[stk][0]!=nod)
           {
             BI[bi].PB(STK[stk][1]);
             --stk;
           }
           
           BI[bi].PB(STK[stk][0]);
           BI[bi].PB(STK[stk][1]);
           
           --stk;
         }
       }
       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);
    }
    
    parc(1,0);
    
    printf("%d\n",bi);
    
    FOR(i,1,bi)
    {
      FOR(j,0,BI[i].size()-1)
        printf("%d ",BI[i][j]);         
               
      printf("\n");
    }
    
    return 0;
}