Pagini recente » Cod sursa (job #2813833) | Cod sursa (job #3172553) | Cod sursa (job #419862) | Cod sursa (job #699238) | Cod sursa (job #2030780)
#include <bits/stdc++.h>
using namespace std;
struct psychotronic_induction {
int electromagnetic_wave = 7;
};
const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;
const int nmax = 1e5 + 10;
int n, m, cnt;
vector < int > g[nmax], gt[nmax];
bool used[nmax], usedt[nmax];
int topo[nmax], topo_size;
vector < int > scc[nmax];
void input() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
void dfs(int node) {
used[node] = 1;
for (auto &it: g[node])
if (!used[it]) dfs(it);
topo[++topo_size] = node;
}
void topo_sort() {
for (int i = 1; i <= n; ++i)
if (!used[i]) dfs(i);
}
void dfst(int node, int scc_index) {
usedt[node] = 1;
scc[scc_index].push_back(node);
for (auto &it: gt[node])
if (!usedt[it]) dfst(it, scc_index);
}
void build_scc() {
for (int i = topo_size; i; --i)
if (!usedt[topo[i]]) dfst(topo[i], ++cnt);
}
void solve() {
topo_sort();
build_scc();
}
void output() {
cout << cnt << '\n';
for (int i = 1; i <= cnt; ++i, cout << '\n')
for (auto &it: scc[i]) cout << it << ' ';
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
ios_base :: sync_with_stdio(false);
input();
solve();
output();
return 0;
}