Pagini recente » Cod sursa (job #1896443) | Cod sursa (job #3253071) | Cod sursa (job #32887) | Cod sursa (job #1297495) | Cod sursa (job #316853)
Cod sursa(job #316853)
# 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;
}