Pagini recente » Cod sursa (job #3335173) | Cod sursa (job #3325925) | Borderou de evaluare (job #1068862) | Cod sursa (job #3322873) | Cod sursa (job #3317003)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> g, gt;
vector<int> order, comp;
vector<int> visited;
void dfs1(int v) {
visited[v] = 1;
for (int u : g[v])
if (!visited[u])
dfs1(u);
order.push_back(v);
}
void dfs2(int v) {
visited[v] = 1;
comp.push_back(v);
for (int u : gt[v])
if (!visited[u])
dfs2(u);
}
int main() {
int n, m;
fin >> n >> m;
g.assign(n + 1, {});
gt.assign(n + 1, {});
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
visited.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!visited[i])
dfs1(i);
visited.assign(n + 1, 0);
vector<vector<int>> comps;
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
if (!visited[v]) {
comp.clear();
dfs2(v);
comps.push_back(comp);
}
}
fout << comps.size() << "\n";
for (auto &c : comps) {
for (int v : c) fout << v << " ";
fout << "\n";
}
return 0;
}