Pagini recente » Cod sursa (job #1636770) | Cod sursa (job #2336031) | Cod sursa (job #601025) | Cod sursa (job #2590844) | Cod sursa (job #3196945)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's the baby, that's not my baby
typedef long long ll;
const int NMAX = 1e5;
bool vis[NMAX + 1];
std::vector<int> order, cur;
std::vector<int> g[NMAX + 1], gg[NMAX + 1];
void dfs0(int u) {
vis[u] = true;
for (const auto &v : g[u]) {
if (!vis[v]) {
dfs0(v);
}
}
order.push_back(u);
}
void dfs(int u) {
vis[u] = true;
cur.push_back(u);
for (const auto &v : gg[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
#ifndef LOCAL
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
while (m--) {
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
gg[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs0(i);
}
}
std::reverse(order.begin(), order.end());
for (int i = 1; i <= n; i++) {
vis[i] = false;
}
std::vector<std::vector<int>> comp;
for (const auto &u : order) {
if (!vis[u]) {
cur.clear();
dfs(u);
comp.push_back(cur);
}
}
std::cout << (int) comp.size() << '\n';
for (auto &w : comp) {
std::sort(w.begin(), w.end());
for (const auto &v : w) {
std::cout << v << ' ';
}
std::cout << '\n';
}
return 0;
}