kosaraju.list.cpp

#include <stdio.h>
#define MAXN 100005
#define FIN "ctc.in"
#define FOUT "ctc.out"

struct Node {
       int y;
       Node *next;
} *L1[ MAXN ], //first list
  *L2[ MAXN ], //second list
  *Comp[ MAXN ];//this array of pointers holds the strongly connected connex.

int countComp = 0;
int post[ MAXN ];
int visited[ MAXN ];

int nodes,//number of nodes
    edges;//number of edges

void DFS(int node) {

     visited[ node ] = 1;

     for(Node *q = L1[ node ]; q; q = q->next) {

          if(!visited[ q->y ]) {

              DFS( q->y );
          }
     }

     post[ ++post[ 0 ] ] = node;
};

void DFSR(int node) {
    
     visited[ node ] = 0;
 
     Node *q = new Node;
     q->y = node;
     q->next = Comp[ countComp ];
     Comp[ countComp ] = q; 
     

     for(Node *q = L2[ node ]; q; q = q->next) {

          if(visited[ q->y ] == 1) {

              DFSR( q->y );
          }
     }     
};

void readData() {

    Node *q1, *q2;

    int x,
        y;

    FILE *in = fopen(FIN, "r");

    fscanf(in, "%d %d", &nodes, &edges);

    while(edges--) {
    
         fscanf(in, "%d %d", &x, &y);
         
         q1 = new Node;
         q1->y = y;
         q1->next = L1[ x ];
         L1[ x ] = q1;  

         q2 = new Node;
         q2->y = x;
         q2->next = L2[ y ];
         L2[ y ] = q2;  

    }

    fclose( in ); 
}

void Kosaraju() {

    for(int node = 1; node <= nodes; node++) {

        if( !visited[ node ] ) {

             DFS( node ); 
        }
    }
 
    for(int i = nodes; i >= 1; --i) {

        if(visited[ post[ i ] ] == 1) {

           ++countComp;
            
           DFSR( post[ i ] ); 
        }   
    }
}

void writeComponents() {

    FILE *out = fopen(FOUT, "w");
   
    fprintf(out, "%d\n", countComp);
   
    for(int i = 1; i <= countComp; ++i, fprintf(out, "\n")) {

        for(Node *R = Comp[ i ]; R; R = R->next) {

            fprintf(out, "%d ", R->y);
        } 
    }
 
    fclose( stdout );
}

int main() {

    readData();
    Kosaraju();
    writeComponents();

 return(0); 
};