Pagini recente » Cod sursa (job #2187062) | Cod sursa (job #1250393) | Cod sursa (job #2118231) | Cod sursa (job #413488) | Cod sursa (job #3271152)
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define sz(x) (int)(x.size())
#define all(a) a.begin(), a.end()
#define nl '\n'
const int N = 3e5 + 5, INF = 1e9, mod = 998244353;
int n, m, ctc, used[N];
vector<int> g[N], gt[N], scc[N];
stack<int> stk;
void dfs1(int node) {
used[node] = 1;
for (auto it : g[node]) {
if (!used[it]) {
dfs1(it);
}
}
stk.push(node);
}
void dfs2(int node) {
used[node] = 1;
scc[ctc].pb(node);
for (auto it : gt[node]) {
if (!used[it]) {
dfs2(it);
}
}
}
void run_case(int test_case) {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
gt[v].pb(u);
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
dfs1(i);
}
}
for (int i = 1; i <= n; i++) {
used[i] = 0;
}
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (!used[node]) {
++ctc;
dfs2(node);
}
}
cout << ctc << '\n';
for (int i = 1; i <= ctc; i++) {
for (auto it : scc[i]) {
cout << it << ' ';
}
cout << '\n';
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int T = 1;
///cin >> T;
for (int t = 1; t <= T; ++t) {
#ifdef _DEBUG
cerr << "=== Subtask " << t << " ===" << '\n';
#endif
run_case(t);
#ifdef _DEBUG
cerr << nl;
#endif
}
}