Pagini recente » Cod sursa (job #529367) | Cod sursa (job #2162120) | Cod sursa (job #1003105) | Cod sursa (job #3264504) | Cod sursa (job #1365305)
#include<fstream>
#include<vector>
using namespace std;
fstream in ( "ctc.in" , ios::in ),
out( "ctc.out", ios::out);
int n, m, c, comp, st[100001];
vector<int> u[100001], p[100001], a[100001];
bool vizu[100001], vizp[100001];
void dfs1(int x){
vizu[x] = true;
for(int i=0; i<u[x].size(); i++){
if( !vizu[ u[x][i] ] ){
dfs1( u[x][i] );
}
}
st[ ++c ] = x;
}
void dfs2(int x){
vizp[x] = true;
for( int i=0; i<p[x].size(); i++){
if( !vizp[ p[x][i] ]){
dfs2( p[x][i] );
}
}
a[ comp ].push_back( x );
}
int main(){
int y, x;
in >> n >> m;
for(int i=0; i<m; i++){
in >> x >> y;
u[x].push_back( y );
p[y].push_back( x );
}
for(int i=1; i<=n; i++){
if( !vizu[i] ){
dfs1( i );
}
}
for(int i=n; i>=1; i--){
if( !vizp[ st[i] ] ){
++comp;
dfs2( st[i] );
}
}
out << comp <<'\n';
for(int i=1; i<=comp; i++){
for(int j=0; j<a[i].size(); j++){
out<< a[i][j] <<' ';
}
out<<'\n';
}
return 0;
}