Pagini recente » Cod sursa (job #2550682) | Cod sursa (job #2964219) | Cod sursa (job #1347970) | Cod sursa (job #2432374) | Cod sursa (job #2741076)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
const int NMAX = 1e5;
std::vector<int> graph[1 + NMAX];
std::vector<int> transposed_graph[1 + NMAX];
std::vector<int> list;
bool vis[1 + NMAX];
std::vector<std::vector<int>> scc;
void dfs(int node) {
vis[node] = true;
for (int nb: graph[node]) {
if (!vis[nb])
dfs(nb);
}
list.push_back(node);
}
void dfs_transposed(int node) {
vis[node] = true;
for (int nb: transposed_graph[node]) {
if (!vis[nb])
dfs_transposed(nb);
}
scc.back().push_back(node);
}
int main() {
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
int n, m;
in >> n >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
in >> a >> b;
graph[a].push_back(b);
transposed_graph[b].push_back(a);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i])
dfs(i);
}
memset(vis, 0, sizeof(vis));
for (int i = (int)list.size() - 1; i >= 0; --i) {
if (!vis[list[i]]) {
scc.emplace_back();
dfs_transposed(list[i]);
}
}
out << scc.size() << '\n';
for (auto& comp: scc) {
for (auto& i: comp)
out << i << ' ';
out << '\n';
}
return 0;
}