Pagini recente » Cod sursa (job #1939081) | Cod sursa (job #3191081) | Cod sursa (job #2376486) | Cod sursa (job #1039111) | Cod sursa (job #3252937)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<bool> viz;
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; cin >> n >> m;
vector<vector<int>> edges(n);
vector<vector<int>> rev_edges(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b; a--; b--;
edges[a].push_back(b);
rev_edges[b].push_back(a);
}
viz.resize(n);
vector<int> st;
for (int node = 0; node < n; node++) {
if( !viz[node] ) {
dfs(node, edges, st);
}
}
viz.clear();
viz.resize(n);
vector<vector<int>> ctc;
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;
}