Pagini recente » Cod sursa (job #359672) | Borderou de evaluare (job #1058383) | Cod sursa (job #259709) | Cod sursa (job #2214971) | Cod sursa (job #3354444)
#include <stdio.h>
#include <stdbool.h>
#define N 100000
#define M 200000
#define NIL (-1)
struct element {
int varf, urm;
};
typedef struct element element;
element v[2*M], ctc[2*M];
int lst_s[N+1], lst_p[N+1], nr_v, stiva[N], vf, lst_ctc[N+1];
bool viz[N+1];
void adauga(int x, int y) {
// il adaugam pe y in lista de succesori a lui x
v[nr_v].varf = y;
v[nr_v].urm = lst_s[x];
lst_s[x] = nr_v++;
// il adaugam pe x in lista de predecesori a lui y
v[nr_v].varf = x;
v[nr_v].urm = lst_p[y];
lst_p[y] = nr_v++;
}
void dfs_s(int x) {
viz[x] = true;
for (int p = lst_s[x]; p != NIL; p = v[p].urm) {
int y = v[p].varf;
if (!viz[y]) {
dfs_s(y);
}
}
stiva[++vf] = x;
}
void dfs_p(int x, int nr_ctc) {
viz[x] = true;
// il adaugam pe x in lista de varfuri a ctc a lui x
ctc[nr_v].varf = x;
ctc[nr_v].urm = lst_ctc[nr_ctc];
lst_ctc[nr_ctc] = nr_v++;
// parcurgeme predecesorii
for (int p = lst_p[x]; p != NIL; p = v[p].urm) {
int y = v[p].varf;
if (!viz[y]) {
dfs_p(y, nr_ctc);
}
}
}
int main() {
FILE *in, *out;
in = fopen("ctc.in", "r");
out = fopen("ctc.out", "w");
int m, n;
fscanf(in, "%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
lst_p[i] = lst_s[i] = NIL;
}
for (int i = 0; i < m; i++) {
int x, y;
fscanf(in, "%d%d", &x, &y);
adauga(x, y);
}
fclose(in);
// etapa 1: (pseudo)sortarea totpologica
vf = -1;
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs_s(i);
}
}
// etapa 2: construim ctc pe baza stivei
for (int i = 1; i <= n; i++) {
lst_ctc[i] = NIL;
viz[i] = false;
}
int nr_ctc = 0;
nr_v = 0;// il refolosim pentru a construi listele cu ctc
while (vf >= 0) {
if (!viz[stiva[vf]]) {
dfs_p(stiva[vf], ++nr_ctc);
}
vf--;
}
fprintf(out, "%d\n", nr_ctc);
for (int i = 1; i <= nr_ctc; i++) {
for (int p = lst_ctc[i]; p != NIL; p = ctc[p].urm) {
fprintf(out, "%d ", ctc[p].varf);
}
fprintf(out, "\n");
}
fclose(out);
return 0;
}