Pagini recente » Cod sursa (job #552941) | Cod sursa (job #1164985) | Cod sursa (job #1351449) | Cod sursa (job #1449077) | Cod sursa (job #2216114)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int MAXN = 1e5;
const int MAXM = 2e5;
vector<int> g1[MAXN + 1], g2[MAXN + 1];
int n, m, cnt;
vector<int> ctc[MAXN + 1], nodes;
bool viz[MAXN + 1];
void dfs1(int node) {
viz[node] = 1;
for (auto x : g1[node]) {
if (!viz[x]) {
nodes.push_back(x);
dfs1(x);
}
}
}
void dfs2(int node) {
ctc[cnt].push_back(node);
viz[node] = 0;
for (auto x : g2[node]) {
if (viz[x]) {
dfs2(x);
}
}
}
int main() {
in >> n >> m;
for (int i = 1; i <= m; ++ i) {
int a, b;
in >> a >> b;
g1[a].push_back(b);
g2[b].push_back(a);
}
for (int i = 1; i <= n; ++ i) {
if (!viz[i]) {
dfs1(i);
}
}
for (auto x : nodes) {
if (viz[x]) {
++ cnt;
dfs2(x);
}
}
out << cnt << '\n';
for (int i = 1; i <= cnt; ++ i) {
for (auto x : ctc[i]) {
out << x << ' ';
}
out << '\n';
}
return 0;
}