Pagini recente » Cod sursa (job #2085359) | Cod sursa (job #2085367)
#include <iostream>
#include <fstream>
#include <vector>
std::vector<int> v[100001], vt[100001], sol[100001];
int n, nrSol;
std::vector<int> postordine;
bool viz[100001] = {false};
void DFS(int k) {
viz[k] = true;
for (int i = 0; i < v[k].size(); i++) {
if (!viz[v[k][i]]) {
DFS(v[k][i]);
}
}
postordine.push_back(k);
}
void DFST(int k) {
viz[k] = false;
sol[nrSol].push_back(k);
for (int i = 0; i < vt[k].size(); i++) {
if (viz[vt[k][i]]) {
DFST(vt[k][i]);
}
}
}
void citire() {
std::ifstream fin("ctc.in");
int m, x, y;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
fin.close();
}
int main(int argc, char *argv[]) {
citire();
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
DFS(i);
}
}
for (int i = postordine.size() - 1; i >= 0; i--) {
if (viz[postordine[i]]) {
nrSol++;
DFST(postordine[i]);
}
}
std::ofstream fout("ctc.out");
fout << nrSol << "\n";
for (int i = nrSol; i >= 0; i--) {
for (int j = 0; j < sol[i].size(); j++) {
fout << sol[i][j] << " ";
}
fout << "\n";
}
fout.close();
return 0;
}