Cod sursa(job #1204612)

Utilizator xtreme77Patrick Sava xtreme77 Data 3 iulie 2014 14:32:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <bitset>

#define rint register int
#define pb push_back

const char IN[] = "ctc.in";
const char OUT[] = "ctc.out";
const int MAX = 100014;

using namespace std;
vector <int> grpl[MAX] , grmn[MAX] , sol[MAX] ;
bitset <MAX> viz;
int n,ordine[MAX],n_sol;
void dfscuplus(int nod);
void dfscuminus(int nod);
int main()
{
    int m;
    freopen( IN , "r" , stdin );
    freopen( OUT , "w" , stdout );
    scanf( "%d%d" , &n , &m );
    while( m-- ){
        int x,y;
        scanf( "%d%d" , &x , &y );
        grpl[x].pb(y);
        grmn[y].pb(x);
    }
    for( rint i = 1 ; i <= n ; ++ i )
        if(!viz[i])
            dfscuplus(i);
    for( rint i = ordine[0] ; i > 0 ; -- i )
        if(viz[ordine[i]]){
            ++n_sol,
            dfscuminus(ordine[i]);
        }
    printf("%d\n",n_sol);
    for( rint i = 1 ; i <= n_sol ; ++ i , printf("\n") )
        for( rint j = 0 ; j<(int)sol[i].size() ; ++ j )
            printf("%d ",sol[i][j]);
    return 0;
}
void dfscuplus(int nod)
{
    viz[nod]=1;
    for( rint i = 0 ; i < (int) grpl[nod].size() ; ++ i )
        if( ! viz[ grpl[nod][i] ] ){
            dfscuplus( grpl[nod][i] );
        }
    ordine[++ordine[0]]=nod;

}
void dfscuminus(int nod)
{
    viz[nod]=0;
    sol[n_sol].pb(nod);
    for( rint i = 0 ; i < (int) grmn[nod].size() ; ++ i )
        if( viz[ grmn[nod][i] ] ){
            dfscuminus( grmn[nod][i] );
        }
}