Pagini recente » Cod sursa (job #3153316) | Cod sursa (job #790559) | Cod sursa (job #988700) | Cod sursa (job #953541) | Cod sursa (job #1227157)
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <bitset>
#include <set>
#define DIM 100009
#define pb push_back
using namespace std;
ofstream out("ctc.out");
int n , m , nrc , nr;
int postord[DIM] ;
bitset < DIM > uz;
vector < int > G[DIM] , GT[DIM] ;
typedef vector < int >:: iterator IT;
set < int > sol[DIM];
typedef set < int >:: iterator JT;
void read();
void dfs( int root );
void dft( int root , int nrc , set < int >* sol );
void solve();
void wrs();
int main()
{
read();
solve();
wrs();
return 0;
}
void read()
{
ifstream in("ctc.in");
in >> n >> m ;
for( int x , y ; m ; --m )
{
in >> x >> y;
G[x].pb(y);
GT[y].pb(x);
}
}
void dfs( int root )
{
uz[ root ] = 1;
for ( IT i = G[root].begin() ; i!= G[root].end(); ++i )
if( !uz[*i] )
dfs(*i);
postord[ ++nr ] = root;
}
void dft( int root , int nrc , set < int >* sol )
{
uz[root] = 0;
sol[nrc].insert(root);
for( IT i = GT[root].begin() ; i!=GT[root].end(); ++i )
if( uz[*i] )
dft(*i,nrc,sol);
}
void solve()
{
for( int i=1 ; i<=n ; i++)
if( !uz[i] )
dfs(i);
for( int i = n ; i >=1 ; i-- )
if( uz[ postord[i] ] )
{
++nrc;
dft(postord[i],nrc,sol);
}
}
void wrs()
{
out << nrc << '\n';
for( int i=1 ; i<=nrc ; i++)
{
for( JT j = sol[i].begin() ; j!=sol[i].end() ; ++j )
out << *j << " ";
out << '\n';
}
}