Pagini recente » Cod sursa (job #1123898) | Cod sursa (job #213738) | Istoria paginii runda/simulare04032019/clasament | Cod sursa (job #1650476) | Cod sursa (job #1605751)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
const char IN [ ] = "ctc.in" ;
const char OUT [ ] = "ctc.out" ;
using namespace std ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
const int MAX = 1e5 + 14 ;
vector < int > gr [ MAX ] ;
vector < int > inv [ MAX ] ;
bitset < MAX > viz ;
vector < int > descopera ;
int cate ;
vector < int > ctc [ MAX ] ;
inline void dfs ( int nod )
{
viz [ nod ] = 1 ;
for ( auto x : gr [ nod ] )
if ( viz [ x ] == 0 )
dfs ( x ) ;
descopera.pb ( nod ) ;
}
inline void dfs2 ( int nod )
{
ctc [ cate ].pb ( nod ) ;
viz [ nod ] = 0 ;
for ( auto x : inv [ nod ] )
if ( viz [ x ] == 1 )
dfs2 ( x ) ;
}
int main()
{
int n , m ;
cin >> n >> m ;
while ( m -- )
{
int x , y ;
cin >> x >> y ;
gr [ x ].pb ( y ) ;
inv [ y ].pb ( x ) ;
}
FORN ( i , 1 , n )
if ( !viz [ i ] ){
dfs ( i ) ;
}
reverse ( descopera.begin() , descopera.end() ) ;
for ( auto x : descopera )
if ( viz [ x ] ) {
++ cate ;
dfs2 ( x ) ;
}
cout << cate << '\n' ;
FORN ( i , 1 , cate ){
for ( auto x : ctc [ i ] )
cout << x << ' ' ;
cout << '\n' ;
}
return 0;
}