Pagini recente » Cod sursa (job #1679980) | Cod sursa (job #1118667) | Cod sursa (job #2626521) | Cod sursa (job #2160658) | Cod sursa (job #2081636)
#include <cstdio>
#include <vector>
const int MAXN = 1e5;
std::vector <int> g[MAXN + 1], con;
std::vector <std::vector <int> > ctc;
int d[MAXN + 1], idx[MAXN + 1],
st[MAXN + 1], top, lidx;
bool inst[MAXN + 1];
static inline int min(int a, int b) {
return a > b ? b : a;
}
void tarjan(int u) {
st[top++] = u;
inst[u] = 1;
d[u] = idx[u] = lidx++;
for (auto v: g[u]) {
if (!idx[v]) {
tarjan(v);
}
if (inst[v]) {
d[u] = min(d[u], d[v]);
}
}
if (d[u] == idx[u]) {
int v;
con.clear();
do {
v = st[--top];
inst[v] = 0;
con.push_back(v);
} while (u != v);
ctc.push_back(con);
}
}
int main() {
int n, m, u, v;
FILE *f = fopen("ctc.in", "r");
fscanf(f, "%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
fscanf(f, "%d%d", &u, &v);
g[u].push_back(v);
}
fclose(f);
lidx = 1;
for (int i = 1; i <= n; ++i) {
if (!idx[i]) {
tarjan(i);
}
}
f = fopen("ctc.out", "w");
fprintf(f, "%d\n", ctc.size());
for (int i = 0; i < ctc.size(); ++i) {
for (int j = 0; j < ctc[i].size(); ++j) {
fprintf(f, "%d ", ctc[i][j]);
}
fprintf(f, "\n");
}
fclose(f);
return 0;
}