Pagini recente » Cod sursa (job #621930) | Cod sursa (job #522661) | Cod sursa (job #787015) | Cod sursa (job #2861334) | Cod sursa (job #2789440)
#include <bits/stdc++.h>
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
constexpr int N = 1e5 + 1;
std::vector<int> g[N];
std::vector<int> gt[N];
std::vector<int> ans[N];
int ts[N];
bool vis[N];
int tsi;
void tsort_dfs(int u) {
vis[u] = true;
for (auto v : g[u]) {
if (!vis[v]) {
tsort_dfs(v);
}
}
ts[tsi--] = u;
}
int cnt;
bool dfst_print;
void dfst(int u) {
vis[u] = true;
if (dfst_print) {
out << u << ' ';
}
for (auto v : gt[u]) {
if (!vis[v]) {
dfst(v);
}
}
}
int main() {
int n, m;
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);
}
tsi = n;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
tsort_dfs(i);
}
}
std::fill(vis + 1, vis + n + 1, false);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (vis[ts[i]]) {
continue;
}
++cnt;
dfst(ts[i]);
}
out << cnt << '\n';
std::fill(vis + 1, vis + n + 1, false);
dfst_print = true;
for (int i = 1; i <= n; ++i) {
if (vis[ts[i]]) {
continue;
}
dfst(ts[i]);
out << '\n';
}
}