Cod sursa(job #317819)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 25 mai 2009 11:53:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
# include <algorithm>
using namespace std;

# define DIM 1 << 17

struct ctc {

    int ant;
    char f;
};

struct graf {

    int nod;
    graf *urm;
};

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

void add0 ( int x, int y ) {

    graf *p = new graf;

    p->nod = y;
    p->urm = lst0[ x ];
    lst0[ 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 ].ant ].ant = nod;
}

void add1 ( int x, int y ) {

    graf *p = new graf;

    p->nod = y;
    p->urm = lst1[ x ];
    lst1[ x ] = p;
}

void df1 ( int nod ) {

    graf *p = new graf;

    a[ nod ].f = 0;
    p->nod = nod;
    p->urm = sol[ nrsol ];
    sol[ nrsol ] = p;
    for ( p = lst1[ nod ]; p; p = p->urm )
        if ( a[ p->nod ].f )
            df1 ( p->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;

    for ( i = 1; i <= n; ++ i )
        if ( !a[ i ].f )
            df0 ( i );
    for ( i = n; i > 0; -- i )
        if ( a[ a[ i ].ant ].f ) {

            ++ nrsol;
            df1 ( a[ i ].ant );
        }
}

void print () {

    int i;
    graf *p;

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

    for ( i = 1; i <= nrsol; 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 ();
    print ();

    return 0;
}