Cod sursa(job #780354)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 20 august 2012 13:23:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
/*Algoritmul lui Tarjan*/
#include<cstdio>
#include<list>
#include<stack>
#include<vector>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int N,M,i,j,x,y,color[100003],index[100003],low[100003],ind,q,nrctc;
list<int> L[100003];
stack<int> S;
vector<int> V[100003];

void parcurge(int x)
{ind++;
 color[x]=GRAY;
 index[x]=ind;
 low[x]=ind;
 S.push(x);
 list<int>::iterator it;
 for(it=L[x].begin(); it!=L[x].end(); it++)
  {if(color[*it]==WHITE)
     {parcurge(*it);
      if(low[*it]<low[x])
        low[x]=low[*it];}
   if(color[*it]==GRAY)
     {if(low[*it]<low[x])
       low[x]=low[*it];}
  }
  
 if(low[x]==index[x])
   {nrctc++;
    do
      {q=S.top();
       V[nrctc].push_back(q);
       color[q]=BLACK;
       S.pop();
       } while(q!=x);    
    } 
}

int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&N,&M);
for(i=1; i<=M; i++)
 {scanf("%d %d",&x,&y);
  L[x].push_back(y);}
for(i=1; i<=N; i++)
  {if(color[i]==WHITE)
     parcurge(i);}
printf("%d\n",nrctc);   
//vector<int>::iterator it;  
for(i=1; i<=nrctc; i++)
 {for(j=0; j<V[i].size(); j++)
     printf("%d ",V[i][j]);
 printf("\n");}    
 
return 0;}