Pagini recente » Cod sursa (job #2036828) | Cod sursa (job #608739) | Cod sursa (job #1463343) | Cod sursa (job #62430) | Cod sursa (job #2847053)
#include <bits/stdc++.h>
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
const int N = 1e5 + 1;
int n, m;
std::vector<int> g[N], gt[N];
bool vis[N];
std::vector<int> topsort() {
std::vector<int> res{{}};
res.reserve(n);
std::function<void(int)> dfs = [&](int u) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) {
dfs(v);
}
}
res.push_back(u);
};
for (int u = 1; u <= n; ++u) {
if (!vis[u]) {
dfs(u);
}
}
std::reverse(res.begin(), res.end());
return res;
}
bool traverse_print = false;
void traverse_component(int u) {
vis[u] = true;
if (traverse_print) {
out << u << ' ';
}
for (int v : gt[u]) {
if (!vis[v]) {
traverse_component(v);
}
}
}
int main() {
in >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
in >> u >> v;
g[u].push_back(v);
gt[v].push_back(u);
}
auto topord = topsort();
std::fill(vis + 1, vis + n + 1, false);
int cnt = 0;
for (int u : topord) {
if (!vis[u]) {
++cnt;
traverse_component(u);
}
}
out << cnt - 1 << '\n';
std::fill(vis + 1, vis + n + 1, false);
traverse_print = true;
for (int u : topord) {
if (!vis[u]) {
traverse_component(u);
out << '\n';
}
}
}