Pagini recente » Cod sursa (job #3219938) | Cod sursa (job #2562922) | Cod sursa (job #2998868) | Cod sursa (job #1325981) | Cod sursa (job #2777985)
#include <fstream>
#include <vector>
std::ifstream fin ("ctc.in");
std::ofstream fout ("ctc.out");
int const nmax = 100000;
std::vector <int> adj1[nmax + 5];
std::vector <int> adj2[nmax + 5];
std::vector <int> list;
std::vector <std::vector <int>> ans;
bool viz[nmax + 5];
bool added[nmax + 5];
void dfs (int x) {
viz[x] = true;
int lim = adj1[x].size();
for (int i = 0; i < lim; i++)
if (!viz[adj1[x][i]])
dfs (adj1[x][i]);
list.push_back(x);
}
int cnt;
void build_ctc (int x) {
added[x] = true;
int lim = adj2[x].size();
ans[cnt].push_back(x);
for (int i = 0; i < lim; i++)
if (!added[adj2[x][i]])
build_ctc (adj2[x][i]);
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y; fin >> x >> y;
adj1[x].push_back(y);
adj2[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs (i);
for (int i = n - 1; i >= 0; i--)
if (!added[list[i]]) {
ans.push_back({});
build_ctc (list[i]);
cnt++;
}
fout << cnt << "\n";
for (int i = 0; i < cnt; i++, fout << "\n") {
int lim = ans[i].size();
for (int x = 0; x < lim; x++)
fout << ans[i][x] << " ";
}
return 0;
}