Cod sursa(job #3354444)

Utilizator rapidu36Victor Manz rapidu36 Data 18 mai 2026 08:15:14
Problema Componente tare conexe Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#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;
}