Cod sursa(job #1652218)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 14 martie 2016 19:38:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

const int N_max = 100005;
const int M_max = 200005;

int vf_1[M_max];
int urm_1[M_max];
int lst_1[N_max];
int nr_1;

int vf_2[M_max];
int urm_2[M_max];
int lst_2[N_max];
int nr_2;

int vf_3[M_max];
int urm_3[M_max];
int lst_3[N_max];
int nr_3;

bool viz_1[N_max];
bool viz_2[N_max];

int C[N_max];
int K;

int sol;

int N, M;

void adauga_1(int x, int y)
{
    // ADAUGA IN LISTA LUI x PE y

    nr_1++;
    vf_1[nr_1] = y;
    urm_1[nr_1] = lst_1[x];
    lst_1[x] = nr_1;
}

void adauga_2(int x, int y)
{
    // ADAUGA IN LISTA LUI x PE y

    nr_2++;
    vf_2[nr_2] = y;
    urm_2[nr_2] = lst_2[x];
    lst_2[x] = nr_2;
}

void adauga_3(int x, int y)
{
    // ADAUGA IN LISTA LUI x PE y

    nr_3++;
    vf_3[nr_3] = y;
    urm_3[nr_3] = lst_3[x];
    lst_3[x] = nr_3;
}

void dfs_1(int x)
{
    int y, p;

    viz_1[x] = true;

    // PARCURG VECINII y AI LUI x

    p = lst_1[x];

    while(p != 0)
    {
        y = vf_1[p];

        if(!viz_1[y]) dfs_1(y);

        p = urm_1[p];
    }

    C[++K] = x;
}

void dfs_2(int x)
{
    int y, p;

    viz_2[x] = true;

    //cout << x << " ";

    adauga_3(sol, x);

    // PARCURG VECINII y AI LUI x

    p = lst_2[x];

    while(p != 0)
    {
        y = vf_2[p];

        if(!viz_2[y]) dfs_2(y);

        p = urm_2[p];
    }
}

int main()
{
    int i, x, y, p;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y;

        adauga_1(x, y);

        adauga_2(y, x); // GRAF TRANSPUS
    }

    for(i = 1; i <= N; i++)
        if(!viz_1[i]) dfs_1(i);

    for(i = N; i >= 1; i--)
        if(!viz_2[ C[i] ])
        {
            sol++;

            dfs_2( C[i] );
        }

    out << sol << '\n';

    for(x = 1; x <= sol; x++)
    {
        // PARCURG LISTA VECINILOR y LUI x

        p = lst_3[x];

        while(p != 0)
        {
            y = vf_3[p];

            out << y << " ";

            p = urm_3[p];
        }

        out << '\n';
    }

    return 0;
}