Pagini recente » Cod sursa (job #518039) | Cod sursa (job #740379) | Cod sursa (job #708504) | Cod sursa (job #375412) | Cod sursa (job #2764975)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
vector <int> edges[NMAX + 1];
vector <int> inv[NMAX + 1];
vector <int> ctc[NMAX];
bool viz[NMAX + 1];
int rev[NMAX], j;
void dfs( int node ) {
viz[node] = true;
for ( auto& i : edges[node] ) {
if ( !viz[i] ) {
dfs( i );
}
}
rev[j++] = node;
}
void reset() {
for ( int i = 0; i <= NMAX; i ++ ) {
viz[i] = false;
}
}
void dfs2( int node ) {
ctc[j].push_back( node );
viz[node] = true;
for ( auto& i : inv[node] ) {
if ( !viz[i] ) {
dfs2( i );
}
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, a, b;
fin >> n >> m;
for ( i = 0; i < m; i ++ ) {
fin >> a >> b;
edges[a].push_back( b );
inv[b].push_back( a );
}
for ( i = 1; i <= n; i ++ ) {
if ( !viz[i] )
dfs( i );
}
reset();
j = 0;
for ( i = n - 1; i >= 0; i -- ) {
if ( !viz[rev[i]] ) {
dfs2( rev[i] );
j ++;
}
}
fout << j << '\n';
for ( i = 0; i < j; i ++ ) {
for ( int x = 0; x < ctc[i].size(); x ++ ) {
fout << ctc[i][x] << ' ';
}
fout << '\n';
}
return 0;
}