Pagini recente » Cod sursa (job #1273500) | Cod sursa (job #1654928) | Cod sursa (job #1690432) | Cod sursa (job #3263457) | Cod sursa (job #1584750)
#include <fstream>
#include <vector>
using namespace std;
ofstream fout ( "ctc.out" ) ;
int n , m , vis[100200] , order[100200] , beg , comp ;
vector<int> G[100200] , GT[100200] , C[100200] ;
void read()
{
int x , y ;
freopen ( "ctc.in" , "r" , stdin ) ;
scanf ( "%d %d" , &n , &m ) ;
for ( int i = 1 ; i <= m ; i++ )
{
scanf ( "%d %d" , &x , &y ) ;
G[x].push_back(y) ;
G[y].push_back(x) ;
}
}
void dfs ( int node )
{
vis[node] = 1 ;
for ( vector<int> :: iterator it = G[node].begin() ; it != G[node].end() ; ++it )
if ( !vis[*it] )
dfs(*it) ;
order[++beg] = node ;
}
void dfst ( int node )
{
vis[node] = 0 ;
for ( vector<int> :: iterator it = GT[node].begin() ; it != GT[node].end() ; ++it )
if ( vis[*it] )
dfst(*it) ;
C[comp].push_back(node) ;
}
int main()
{
read() ;
for ( int i = 1 ; i <= n ; ++i )
if ( !vis[i] )
dfs(i) ;
for ( int i = n ; i >= 1 ; --i )
if ( vis[order[i]] )
{
comp++ ;
dfst(order[i]) ;
}
fout << comp << '\n' ;
for ( int i = 1 ; i <= comp ; ++i )
{
for ( vector<int> :: iterator it = C[i].begin() ; it != C[i].end() ; ++it )
fout << *it << ' ' ;
fout << '\n' ;
}
return 0;
}