Pagini recente » Cod sursa (job #3291425) | Cod sursa (job #3293236)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
vector <int> edges[NMAX + 1];
vector <int> trans[NMAX + 1];
vector <int> order;
bool viz[NMAX + 1];
void dfs1( int node ) {
viz[node] = true;
for ( auto vec : edges[node] ) {
if ( !viz[vec] ) dfs1( vec );
}
order.push_back( node );
}
void dfs2( int node ) {
viz[node] = true;
for ( auto vec : trans[node] ) {
if ( !viz[vec] ) dfs2( vec );
}
order.push_back( node );
}
int main() {
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
int n, m;
fin >> n >> m;
for ( int i = 1, a, b; i <= m; i ++ ) {
fin >> a >> b;
edges[a].push_back( b );
trans[b].push_back( a );
}
for ( int i = 1; i <= n; i ++ ) {
if ( !viz[i] ) dfs1( i );
}
reverse( order.begin(), order.end() );
for ( int i = 1; i <= n; i ++ ) viz[i] = false;
vector <vector<int>> comps;
auto aux = order;
for ( auto node : aux ) {
order.clear();
if ( !viz[node] ) {
dfs2( node );
comps.push_back( order );
}
}
fout << comps.size() << '\n';
for ( auto comp : comps ) {
for ( auto node : comp ) fout << node << ' ';
fout << '\n';
}
return 0;
}