Pagini recente » Cod sursa (job #2330869) | Cod sursa (job #1962488) | Cod sursa (job #248547) | Cod sursa (job #1252936) | Cod sursa (job #1657134)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100000;
bool viz[NMAX+2];
vector <int> G[NMAX+2], GP[NMAX+2], ord, ind_ctc;
int N, M;
vector < vector<int> > ctc;
void Dfs_Plus( int nod ) {
viz[nod] = 1;
ord.push_back( nod );
for( int i = 0; i < (int)GP[nod].size(); ++i ) {
int x = GP[nod][i];
if( !viz[x] ) {
Dfs_Plus( x );
}
}
}
void Dfs_Minus( int nod ) {
viz[nod] = 1;
ind_ctc.push_back( nod );
for( int i = 0; i < (int)G[nod].size(); ++i ) {
int x = G[nod][i];
if( !viz[x] ) {
Dfs_Minus( x );
}
}
}
int main() {
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y;
in >> x >> y;
G[x].push_back( y );
GP[y].push_back( x );
}
for( int i = 1; i <= N; ++i ) {
if( !viz[i] ) Dfs_Plus(i);
}
memset( viz, 0, sizeof(viz) );
for( int i = (int)ord.size() - 1; i >= 0; --i ) {
if( !viz[ ord[i] ] ) {
ind_ctc.clear();
Dfs_Minus( ord[i] );
sort( ind_ctc.begin(), ind_ctc.end() );
ctc.push_back( ind_ctc );
}
}
out << (int)ctc.size() << '\n';
for( int i = 0; i < (int)ctc.size(); ++i ) {
for( int j = 0; j < (int)ctc[i].size(); ++j ) out << ctc[i][j] << ' ';
out << '\n';
}
return 0;
}