Pagini recente » Cod sursa (job #3159668) | Cod sursa (job #613486) | Cod sursa (job #2978625) | Cod sursa (job #2142716) | Cod sursa (job #363719)
Cod sursa(job #363719)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NX 100010
vector <int> a[NX];
vector <int> gt[NX];
int t[NX],n,m,ct=0,cc=0, u[NX], b[NX];
void DFS( int v )
{
u[v]=1;
for( vector<int>::iterator it = a[v].begin(); it!= a[v].end(); it++ )
if( !u[*it] )
DFS( *it );
t[v]=ct++;
}
void DFS2( int v )
{
u[v]=cc;
for( vector<int>::iterator it = gt[v].begin(); it!= gt[v].end(); it++ )
if( !u[*it] )
DFS2( *it );
}
struct cmp {
bool operator() ( const int x, const int y ) const {
return t[x] > t[y];
}
};
int main()
{
int i, v, w;
freopen( "ctc.in", "r", stdin);
freopen( "ctc.out", "w", stdout);
scanf( "%d%d", &n, &m );
for( i=0; i<m; i++)
{
scanf( "%d%d", &w, &v);
a[w].push_back(v);
gt[v].push_back(w);
}
for( i = 1; i <= n; i++ )
if( !u[i] )
DFS( i );
for( i = 1; i <= n; i++ )
sort( gt[i].begin(), gt[i].end(), cmp() );
for( i = 1; i <= n; i++ ) {
b[i] = i;
u[i] = 0;
}
sort( b+1, b+n+1, cmp() );
for( i = 1; i <= n; i++ ) {
if( !u[ b[i] ] )
cc++;
DFS2( b[i] );
}
printf( "%d\n", cc );
for( i = 1; i <= cc; i++ ) {
for( int j = 1; j <= n; j++ )
if( u[j] == i )
printf( "%d ", j );
printf( "\n" );
}
return 0;
}