Pagini recente » Cod sursa (job #3346674) | Cod sursa (job #1006917) | Cod sursa (job #1701606) | Cod sursa (job #3305899) | Cod sursa (job #3353863)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int roots[MAXN + 1] , sz[MAXN + 1] , cnt;
bool viz[MAXN + 1];
stack< int >s;
vector< int >edges[MAXN + 1] , redges[MAXN + 1];
vector< int >v[MAXN + 1];
void dfs( int nod ) {
viz[nod] = 1;
for( auto x : edges[nod] )
if( !viz[x] )
dfs( x );
s.push( nod );
}
void dfs2( int nod ) {
if( !roots[nod] )
v[cnt].push_back( nod );
roots[nod] = cnt;
sz[cnt]++;
for( auto x : redges[nod] )
if( !roots[x] )
dfs2( x );
}
int main() {
ifstream cin( "ctc.in" );
ofstream cout( "ctc.out" );
int n , m , k , i , a , b;
cin >> n >> m;
for( i = 1 ; i <= m ; i++ ) {
cin >> a >> b;
edges[a].push_back( b );
redges[b].push_back( a );
}
for( i = 1 ; i <= n ; i++ )
if( !viz[i] )
dfs( i );
cnt = 0;
while( !s.empty() ) {
a = s.top();
s.pop();
if( !roots[a] )
cnt++;
dfs2( a );
}
cout << cnt << '\n';
for( i = 1 ; i <= cnt ; i++ ) {
sort( v[i].begin() , v[i].end() );
for( auto x : v[i] )
cout << x << ' ';
cout << '\n';
}
return 0;
}