Pagini recente » Cod sursa (job #2972442) | Cod sursa (job #15303) | Cod sursa (job #2671323) | Cod sursa (job #1728023) | Cod sursa (job #363718)
Cod sursa(job #363718)
#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( int i=0; i<a[v].size(); i++ )
if( !u[a[v][i]] )
DFS( a[v][i] );
t[v]=ct++;
}
void DFS2( int v )
{
u[v]=cc;
for( int i=0; i<gt[v].size(); i++ )
if( !u[gt[v][i]] )
DFS2( gt[v][i] );
}
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;
}