Cod sursa(job #316853)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 21 mai 2009 13:07:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
# include <algorithm>
using namespace std;

# define DIM 1 << 17

struct ctc {

	int post;
	char f;
};

struct graf {
    
    int nod;
    graf *urm;
};

int n, m, cnt;
ctc a[ DIM ];
graf *sol[ DIM ], *lst0[ DIM ], *lst1[ DIM ];

void add0 ( int x, int y ) {
    
    graf *p = new graf;
    
    p->nod = y;
    p->urm = lst0[ x ];
    lst0[ x ] = p;
}

void add1 ( int x, int y ) {
    
    graf *p = new graf;
    
    p->nod = y;
    p->urm = lst1[ x ];
    lst1[ x ] = p;
}

void df0 ( int nod ) {
    
    graf *p;
    
    a[ nod ].f = 1;
    for ( p = lst0[ nod ]; p; p = p->urm )
        if ( !a[ p->nod ].f )
            df0 ( p->nod );
    a[ ++ a[ 0 ].post ].post = nod;
}

void df1 ( int nod ) {
    
    graf *p = new graf, *q;
    
    a[ nod ].f = 0;
    p->nod = nod;
    p->urm = sol[ cnt ];
    sol[ cnt ] = p;
    for ( q = lst1[ nod ]; q; q = q->urm )
        if ( a[ q->nod ].f )
            df1 ( q->nod );
}

void read () {
    
    int i, x, y;
    
    scanf ( "%d%d", &n, &m );
    for ( i = 0; i < m; ++ i ) {
        
        scanf ( "%d%d", &x, &y );
        add0 ( x, y );
        add1 ( y, x );
    }
}

void solve () {
    
    int i;
    graf *p;
    
    for ( i = 1; i <= n; ++ i )
        if ( !a[ i ].f )
            df0 ( i );
	for ( i = n; i > 0; -- i )
		if ( a[ a[ i ].post ].f ) {

			++ cnt;
			df1 ( a[ i ].post );
		}
    printf ( "%d\n", cnt );
	for ( i = 1; i <= cnt; printf ( "\n" ), ++ i )
        for ( p = sol[ i ]; p; p = p->urm )
            printf ( "%d ", p->nod );
}   

int main () {
    
    freopen ( "ctc.in", "r", stdin );
    freopen ( "ctc.out", "w", stdout );
    
    read ();
    solve ();
    
    return 0;
}