Pagini recente » Cod sursa (job #2062989) | Cod sursa (job #793321) | Cod sursa (job #2914174) | Cod sursa (job #2927048) | Cod sursa (job #3156590)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
bool viz[NMAX + 1];
void dfs( int node, const vector<vector <int>>& edges, vector <int>& order ) {
viz[node] = true;
for ( auto vec : edges[node] ) {
if ( !viz[vec] ) {
dfs( vec, edges, order );
}
}
order.push_back( node );
}
int main() {
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
int n, m;
fin >> n >> m;
vector<vector <int>> edges;
vector<vector <int>> trans;
edges.resize( n );
trans.resize( n );
for ( int i = 1, a, b; i <= m; i ++ ) {
fin >> a >> b; a--; b--;
edges[a].push_back( b );
trans[b].push_back( a );
}
vector <int> order, useless;
for ( int i = 0; i < n; i ++ ) {
if ( !viz[i] ) {
dfs( i, edges, order );
}
}
for ( int i = 0; i < n; i ++ ) viz[i] = false;
reverse( order.begin(), order.end() );
vector <vector<int>> comps;
for ( auto x : order ) {
if ( !viz[x] ) {
comps.push_back( {} );
dfs( x, trans, comps[comps.size() - 1] );
}
}
fout << comps.size() << '\n';
for ( auto comp : comps ) {
for ( auto node : comp ) {
fout << node + 1 << ' ';
}
fout << '\n';
}
return 0;
}