Pagini recente » Cod sursa (job #371602) | Borderou de evaluare (job #1908943) | Cod sursa (job #337767) | Cod sursa (job #2059907) | Cod sursa (job #3309601)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
struct SCC { // 0-indexed
int n;
std::vector<std::vector<int>> g, gg;
std::vector<int> order, cur;
std::vector<bool> vis;
std::vector<int> root;
std::vector<std::vector<int>> comp;
void init(int _n) {
n = _n;
g.resize(n);
gg.resize(n);
order.resize(n);
order.clear();
cur.clear();
root.resize(n);
}
void reset() {
order.clear();
cur.clear();
comp.clear();
for (int i = 0; i < n; i++) {
g[i].clear();
gg[i].clear();
}
}
void addEdge(int u, int v) {
g[u].push_back(v);
gg[v].push_back(u);
}
void dfs0(int u) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) {
dfs0(v);
}
}
order.push_back(u);
}
void dfs(int u) {
vis[u] = true;
cur.push_back(u);
for (int v : gg[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
void build() {
vis.assign(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs0(i);
}
}
vis.assign(n, false);
std::reverse(order.begin(), order.end());
for (int u : order) {
if (!vis[u]) {
cur.clear();
dfs(u);
for (int v : cur) {
root[v] = cur[0];
}
comp.push_back(cur);
}
}
for (auto &v : comp) {
std::sort(v.begin(), v.end());
}
std::sort(comp.begin(), comp.end(), [](auto u, auto v) {
return u[0] < v[0];
});
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
SCC G;
int n, m;
std::cin >> n >> m;
G.init(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
G.addEdge(u, v);
}
G.build();
std::cout << (int) G.comp.size() << '\n';
for (auto v : G.comp) {
for (int x : v) {
std::cout << x + 1 << ' ';
}
std::cout << '\n';
}
return 0;
}