Pagini recente » Cod sursa (job #2823952) | Cod sursa (job #103538) | Cod sursa (job #77322) | Cod sursa (job #3285367) | Cod sursa (job #317820)
Cod sursa(job #317820)
# 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;
}