Pagini recente » Cod sursa (job #316828) | Cod sursa (job #1213892) | Cod sursa (job #1571934) | Cod sursa (job #1475709) | Cod sursa (job #2052894)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MAXN 100000
int vf, k, q, st[MAXN + 1], viz[MAXN + 1], best[MAXN + 1];
bool ok[MAXN + 1];
vector <int> g[MAXN + 1], c[MAXN + 1];
void dfs(int x) {
st[++vf] = x;
viz[x] = best[x] = ++k;
ok[x] = 1;
for (auto &y : g[x]) {
if (viz[y] == 0) {
dfs(y);
best[x] = min(best[x], best[y]);
} else if (ok[y]) best[x] = min(best[x], viz[y]);
}
if (viz[x] == best[x]) {
while (st[vf] != x) {
c[q].push_back(st[vf]);
ok[st[vf]] = 0;
vf--;
}
c[q++].push_back(x);
ok[x] = 0;
vf--;
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
dfs(i);
fout << q << '\n';
for (int i = 0; i < q; i++) {
for (auto &x : c[i])
fout << x << ' ';
fout << '\n';
}
return 0;
}