Pagini recente » Cod sursa (job #52462) | Cod sursa (job #817380) | Cod sursa (job #1080333) | Cod sursa (job #334073) | Cod sursa (job #2870626)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N(1e5 + 5);
int n, m, cnt;
bitset<N> viz;
stack<int> st;
vector<int> g[N], gt[N], ctc[N];
inline void DFS(int const& x) {
viz[x] = 1;
for (int const& y : g[x])
if (!viz[y])
DFS(y);
st.emplace(x);
}
inline void DFSR(int const& x) {
viz[x] = 1;
ctc[cnt].emplace_back(x);
for (int const& y : gt[x])
if (!viz[y])
DFSR(y);
}
void Kosaraju() {
while (!st.empty()) {
int x = st.top();
st.pop();
if (!viz[x]) {
++cnt;
DFSR(x);
}
}
}
main() {
fin >> n >> m;
while (m--) {
int x, y;
fin >> x >> y;
g[x].emplace_back(y);
gt[y].emplace_back(x);
}
for (int i = 1; i <= n; ++i)
if (!viz[i])
DFS(i);
viz.reset();
Kosaraju();
fout << cnt << '\n';
for (int c = 1; c <= cnt; ++c, fout << '\n')
for (int const& x : ctc[c])
fout << x << ' ';
return 0;
}