Cod sursa(job #2478450)

Utilizator unchnounMihai Panduru unchnoun Data 22 octombrie 2019 08:49:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
using namespace std;

int * A[100005], * AT[100005], viz[100005], postordine[100005], nr, * comp_conexe[100005], nr_comp;

void DFS(int x)
{
    viz[x] = 1;
    for (int i = 1; i <= A[x][0]; ++i)
        if (!viz[A[x][i]])
            DFS(A[x][i]);
    postordine[++nr] = x;
}

void DFST(int x)
{
    viz[x] = 0;
    ++comp_conexe[nr_comp][0];
    comp_conexe[nr_comp] = (int *) realloc(comp_conexe[nr_comp], (comp_conexe[nr_comp][0] + 1) * sizeof(int));
    comp_conexe[nr_comp][comp_conexe[nr_comp][0]] = x;
    for (int i = 1; i <= AT[x][0]; ++i)
        if (viz[AT[x][i]])
            DFST(AT[x][i]);
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int varfuri, muchii, i, j;
    fin >> varfuri >> muchii;

    for (i = 1; i <= varfuri; ++i)
    {
        A[i] = (int *) realloc(A[i], sizeof(int)), A[i][0] = 0;
        AT[i] = (int *) realloc(AT[i], sizeof(int)), AT[i][0] = 0;
        comp_conexe[i] = (int *) realloc(comp_conexe[i], sizeof(int)), comp_conexe[i][0] = 0;
    }
    for (i = 1; i <= muchii; ++i)
    {
        int v1, v2;
        fin >> v1 >> v2;
        ++A[v1][0];
        A[v1] = (int *) realloc(A[v1], (A[v1][0] + 1) * sizeof(int));
        A[v1][A[v1][0]] = v2;
        ++AT[v2][0];
        AT[v2] = (int *) realloc(AT[v2], (AT[v2][0] + 1) * sizeof(int));
        AT[v2][AT[v2][0]] = v1;
    }
    for (i = 1; i <= varfuri; ++i)
        if (!viz[i])
            DFS(i);
    for (i = varfuri; i >= 1; --i)
        if (viz[postordine[i]])
        {
            ++nr_comp;
            DFST(postordine[i]);
        }
    fout << nr_comp << "\n";
    for (i = 1; i <= nr_comp; ++i)
    {
        for (j = 1; j <= comp_conexe[i][0]; ++j)
            fout << comp_conexe[i][j] << ' ';
        fout << "\n";
    }
}