Pagini recente » Cod sursa (job #1867676) | Cod sursa (job #132245) | Cod sursa (job #2326157) | Cod sursa (job #572877) | Cod sursa (job #3225657)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 2e5 + 5, mod = 1e9 + 7, inf = 2e18;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
freopen("file.in", "r", stdin);
freopen("file.out", "w", stdout);
#else
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<vector<int>> gt(n + 1);
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
vector<int> ord;
vector<int> viz(n + 1);
function<void(int)> dfs = [&](int x) {
viz[x] = 1;
for (auto y: g[x]) {
if (!viz[y]) {
dfs(y);
}
}
ord.push_back(x);
};
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs(i);
}
}
reverse(ord.begin(), ord.end());
vector<vector<int>> ans;
vector<int> comp;
viz = vector<int>(n + 1, 0);
dfs = [&](int x) {
viz[x] = 1;
comp.push_back(x);
for (auto y: gt[x]) {
if (!viz[y]) {
dfs(y);
}
}
};
for (auto i: ord) {
if (viz[i]) continue;
comp.clear();
dfs(i);
ans.push_back(comp);
}
cout << ans.size() << '\n';
for (auto v: ans) {
for (auto x: v) {
cout << x << ' ';
}
cout << '\n';
}
}