Cod sursa(job #1234775)

Utilizator thinkphpAdrian Statescu thinkphp Data 27 septembrie 2014 23:15:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define MAX 100005
 
using namespace std;
 
int num_nodes,
    num_arcs;
 
int num_comp = 0;
 
vector<int> List1[ MAX ];
vector<int> List2[ MAX ];
vector<int> R[ MAX ];

stack<int> myStack;

bool VIS[MAX]; 
 
//function prototypes
void read();
void DFS1(int node);
void DFS2(int node);
void solve();
void displayList();
void write();
 
int main() {
 
    read();
    solve();
    write();
    
   return(0);
};
 
void read() {
 
     int x,y;
 
     freopen(FIN, "r", stdin);
 
     scanf("%d %d", &num_nodes, &num_arcs);
  
     for(; num_arcs;num_arcs--) {
  
           scanf("%d %d", &x, &y);
           List1[ x ].push_back( y );
           List2[ y ].push_back( x );
     }
     
     fclose( stdin ); 
};
 
void DFS1(int node) {

     VIS[ node ] = true;
 
     for(int i = 0; i < List1[ node ].size(); i++) {
 
             if( !VIS[ List1[ node ][ i ] ]) {
 
                    DFS1( List1[ node ][ i ]);
             }
     }

     myStack.push( node );
};
 
void DFS2(int node) {


     VIS[node] = true;    

     R[ num_comp ].push_back( node );
 
     for(int j = 0; j < List2[ node ].size(); j++) {
 
             if( !VIS[ List2[ node ][ j ] ]) {
 
                    DFS2( List2[ node ][ j ] );
             }
     }
};
 
void write() {
 
    freopen(FOUT, "w", stdout);

    printf("%d\n", num_comp);

    for(int num=1; num<=num_comp; num++) { 

        for(vector<int>::iterator it = R[num].begin(); it != R[num].end(); ++it) {

                     printf("%d ", *it);
        }  

        printf("\n");
    }
 
 
   fclose( stdin );
};
 
void solve() {
 
    for(int i = 1; i <= num_nodes; i++) 

            if( !VIS[ i ] )

                 DFS1( i );

    memset(VIS, false, sizeof(VIS)); 

    while( !myStack.empty() ) {

            int node = myStack.top();

            myStack.pop();

            if( !VIS[ node ] ) {

               ++num_comp;

                DFS2( node );  
            }

    }

}
 
void displayList() {
 
     for(int i = 1; i<=num_nodes; i++) {
 
         printf("%d -> ", i); 
 
         for(int j = 0; j < List2[i].size(); j++) {
 
                  printf("%d ", List2[i][j]);
         }
                  printf("\n");
     }
 
}