Cod sursa(job #3371934)

Utilizator david18.6yDavid Popa david18.6y Data 1 noiembrie 2026 20:45:15
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <cstdio>
#include <cstring>

const int MAXN = 100005;
const int MAXM = 200005;

// lista si lista_compl
int head1[MAXN], nxt1[MAXM], to1[MAXM], cnt1;
int head2[MAXN], nxt2[MAXM], to2[MAXM], cnt2;

int q[MAXN];
bool vazut_plus[MAXN], vazut_minus[MAXN], deja_in_comp[MAXN];
int res[MAXN], start[MAXN];

int main() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) head1[i] = head2[i] = -1;

    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        to1[cnt1] = y; nxt1[cnt1] = head1[x]; head1[x] = cnt1++;  // lista
        to2[cnt2] = x; nxt2[cnt2] = head2[y]; head2[y] = cnt2++;  // lista_compl
    }

    int nc = 0, nn = 0;

    for (int nod = 1; nod <= n; nod++) {
        if (deja_in_comp[nod]) continue;

        // plus: BFS pe graful original
        memset(vazut_plus, 0, sizeof(vazut_plus));
        int h = 0, t = 0;
        q[t++] = nod;
        vazut_plus[nod] = true;
        while (h < t) {
            int varf = q[h++];
            for (int e = head1[varf]; e != -1; e = nxt1[e]) {
                int vecin = to1[e];
                if (!vazut_plus[vecin]) {
                    vazut_plus[vecin] = true;
                    q[t++] = vecin;
                }
            }
        }

        // minus: BFS pe graful transpus
        memset(vazut_minus, 0, sizeof(vazut_minus));
        h = t = 0;
        q[t++] = nod;
        vazut_minus[nod] = true;
        while (h < t) {
            int varf = q[h++];
            for (int e = head2[varf]; e != -1; e = nxt2[e]) {
                int vecin = to2[e];
                if (!vazut_minus[vecin]) {
                    vazut_minus[vecin] = true;
                    q[t++] = vecin;
                }
            }
        }

        // componenta = plus & minus
        start[nc++] = nn;
        for (int x = 1; x <= n; x++) {
            if (vazut_plus[x] && vazut_minus[x]) {
                res[nn++] = x;
                deja_in_comp[x] = true;
            }
        }
    }
    start[nc] = nn;

    printf("%d\n", nc);
    for (int c = 0; c < nc; c++) {
        for (int j = start[c]; j < start[c + 1]; j++)
            printf("%d ", res[j]);
        printf("\n");
    }
    return 0;
}