Pagini recente » Cod sursa (job #2889245) | Cod sursa (job #1212234) | Cod sursa (job #1601789) | Cod sursa (job #1253003) | Cod sursa (job #1248600)
#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>
using namespace std;
void dfs(
const int v,
vector<bool>& visited,
vector<int>& topological_order,
const vector<vector<int>>& G) {
visited[v] = true;
for (int u : G[v]) if (!visited[u])
dfs(u, visited, topological_order, G);
topological_order.push_back(v);
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m; fin >> n >> m;
vector<vector<int>> G(n), rG(n);
for (; m; --m) {
int u, v; fin >> u >> v;
G[u - 1].push_back(v - 1);
rG[v - 1].push_back(u - 1);
}
vector<bool> visited(n, false);
vector<int> topological_order;
for (int v = 0; v < n; ++v) if (!visited[v])
dfs(v, visited, topological_order, G);
fill(visited.begin(), visited.end(), false);
vector<vector<int>> ctc;
for (auto v = topological_order.rbegin(); v < topological_order.rend(); v++)
if (!visited[*v]) {
ctc.push_back(vector<int>());
dfs(*v, visited, ctc.back(), rG);
}
fout << ctc.size() << '\n';
for (vector<int>& c : ctc) {
for (int v : c)
fout << v+1 << ' ';
fout << '\n';
}
return 0;
}