Pagini recente » Cod sursa (job #1391164) | Cod sursa (job #2182193) | Cod sursa (job #2749189) | Cod sursa (job #2132575) | Cod sursa (job #2197858)
#include <fstream>
#include <vector>
#include <stack>
void print_output(std::vector<std::vector<int>> result, std::ofstream &out) {
out << result.size() << '\n';
for (auto &ctc : result) {
for (auto &node : ctc) {
out << node << ' ';
}
out << '\n';
}
}
void dfs(int node, std::vector<int> *adj,std::vector<bool> &visited,
std::stack<int> &kosaraju) {
visited[node] = true;
for (auto &neighbour : adj[node]) {
if (!visited[neighbour]) {
dfs(neighbour, adj, visited, kosaraju);
}
}
kosaraju.push(node);
}
void dfs_transpose(int node, std::vector<int> *adj_transpose,
std::vector<bool> &visited_transpose, std::vector<int> &ctc) {
ctc.push_back(node);
visited_transpose[node] = false;
for (auto &neighbour : adj_transpose[node]) {
if (visited_transpose[neighbour]) {
dfs_transpose(neighbour, adj_transpose, visited_transpose, ctc);
}
}
}
int main() {
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
int n, m;
in >> n >> m;
std::vector<int> adj[n + 1];
std::vector<int> adj_transpose[n + 1];
int i;
int u, v;
for (i = 0; i < m; ++i) {
in >> u >> v;
adj[u].push_back(v);
adj_transpose[v].push_back(u);
}
std::stack<int> kosaraju;
std::vector<bool> visited(n + 1, false);
for (i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, adj, visited, kosaraju);
}
}
std::vector<std::vector<int>> result;
while (!kosaraju.empty()) {
int node = kosaraju.top();
kosaraju.pop();
if (visited[node]) {
std::vector<int> new_ctc;
dfs_transpose(node, adj_transpose, visited, new_ctc);
result.push_back(new_ctc);
}
}
print_output(result, out);
in.close();
out.close();
return 0;
}