Cod sursa(job #2238060)

Utilizator dragos192k1Dragos-Iulian Galeteanu dragos192k1 Data 4 septembrie 2018 14:16:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

int n, m, *a[100005], *atr[100005], checked[100005], postorder[100005], peak, *ctc[100005], nr_ctc;

void dfs(int x)
{
    checked[x] = 1;

    for (int i = 1; i <= a[x][0]; ++i)
        if (!checked[a[x][i]])
            dfs(a[x][i]);

    postorder[++peak] = x;
}

void dfs_tr(int x)
{
    checked[x] = 0;

    ++ctc[nr_ctc][0];
    ctc[nr_ctc] = (int *)realloc(ctc[nr_ctc], (ctc[nr_ctc][0] + 1) * sizeof(int));
    ctc[nr_ctc][ctc[nr_ctc][0]] = x;

    for (int i = 1; i <= atr[x][0]; ++i)
        if (checked[atr[x][i]])
            dfs_tr(atr[x][i]);
}

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

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        a[i] = (int *)realloc(a[i], sizeof(int));
        a[i][0] = 0;
        atr[i] = (int *)realloc(atr[i], sizeof(int));
        atr[i][0] = 0;
        ctc[i] = (int *)realloc(ctc[i], sizeof(int));
        ctc[i][0] = 0;
    }

    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);

        ++a[x][0];
        a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
        a[x][a[x][0]] = y;

        ++atr[y][0];
        atr[y] = (int *)realloc(atr[y], (atr[y][0] + 1) * sizeof(int));
        atr[y][atr[y][0]] = x;
    }

    fclose(in);

    for (int i = 1; i <= n; ++i)
        if (!checked[i])
            dfs(i);

    for (int i = n; i; --i)
        if (checked[postorder[i]]) {
            ++nr_ctc;
            dfs_tr(postorder[i]);
        }

    printf("%d\n", nr_ctc);

    for (int i = 1; i <= nr_ctc; ++i) {
        for (int j = 1; j <= ctc[i][0]; ++j)
            printf("%d ", ctc[i][j]);
        printf("\n");
    }

    fclose(out);
    return 0;
}