Pagini recente » Cod sursa (job #1625497) | Cod sursa (job #2023824) | Cod sursa (job #471585) | Cod sursa (job #752629) | Cod sursa (job #1711725)
#include <stdio.h>
#include <stdlib.h>
#define Smerenie 200000
#define Nadejde 100000
typedef struct {
int v, next;
} list;
int N, M;
int d[Nadejde + 1];
int adj[Nadejde + 1];
list l[Smerenie + 1];
int ss, stack[Nadejde + 1];
char onStack[Nadejde + 1];
int numScc;
int size[Nadejde + 1];
int *scc[Nadejde + 1];
int MIN(int X, int Y) {
return X < Y ? X : Y;
}
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
int tarjan(int u, int depth) {
d[u] = depth;
stack[ss++] = u;
onStack[u] = true;
int pos, v;
for (pos = adj[u]; pos; pos = l[pos].next) {
v = l[pos].v;
if (d[v] == 0) {
d[u] = MIN(d[u], tarjan(v, depth + 1));
} else if (onStack[v]) {
d[u] = MIN(d[u], d[v]);
}
}
if (d[u] == depth) {
int save = ss;
do {
ss--;
} while (stack[ss] != u);
size[numScc] = save - ss;
scc[numScc] = (int*)calloc(size[numScc], sizeof(int));
int ptr = 0;
ss = save;
do {
v = stack[--ss];
onStack[v] = false;
scc[numScc][ptr++] = v;
} while (v != u);
numScc++;
}
return d[u];
}
int main(void) {
FILE *f = fopen("ctc.in", "r");
int i, u, v;
fscanf(f, "%d %d", &N, &M);
while (M) {
fscanf(f, "%d %d", &u, &v);
addEdge(u, v, M);
M--;
}
fclose(f);
for (u = 1; u <= N; u++) {
if (d[u] == 0) {
tarjan(u, 1);
}
}
freopen("ctc.out", "w", stdout);
fprintf(stdout, "%d\n", numScc);
for (i = 0; i < numScc; i++) {
for (u = 0; u < size[i]; u++) {
fprintf(stdout, " %d", scc[i][u]);
}
fprintf(stdout, "\n");
}
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}