Pagini recente » Cod sursa (job #853790) | Cod sursa (job #3162884) | Cod sursa (job #1336410) | Cod sursa (job #312675) | Cod sursa (job #3252946)
#include <vector>
#include <fstream>
using namespace std;
#define nmax 100000
vector <bool> viz;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
void dfs( int node, vector<vector<int>>& edges, vector <int>& add_to ) {
viz[node] = true;
for( auto new_node : edges[node] ) {
if( !viz[new_node] )
dfs( new_node, edges, add_to );
}
add_to.push_back( node );
}
void solve() {
int n, m, x, y;
cin >> n >> m;
vector <vector <int> > edges(n);
vector <vector <int> > rev_edges(n);
vector <vector <int>> ctc;
vector <int> st;
viz.resize(n);
for( int i = 0; i < m; i++ ) {
cin >> x >> y; x--; y--;
edges[x].push_back( y );
rev_edges[y].push_back( x );
}
for (int node = 0; node < n; node++) {
if( !viz[node] ) {
dfs(node, edges, st);
}
}
viz.clear();
viz.resize(n);
for (int i = st.size() - 1; i >= 0; i--) {
if (viz[st[i]] == 0) {
ctc.push_back(vector<int>());
dfs(st[i], rev_edges, ctc.back());
}
}
cout << ctc.size() << "\n";
for ( auto comp : ctc ) {
for (auto node : comp) {
cout << node + 1 << " ";
}
cout << "\n";
}
}
int main() {
solve();
return 0;
}