Cod sursa(job #1637855)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 7 martie 2016 19:41:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 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 vf1[M_max];
int urm1[M_max];
int lst1[N_max];
int nr1;

int vf2[M_max];
int urm2[M_max];
int lst2[N_max];
int nr2;

int vf3[M_max];
int urm3[M_max];
int lst3[N_max];
int nr3;

int sol;

int C[N_max];
int K;

bool viz1[N_max];
bool viz2[N_max];

int N, M;

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

    nr1++;
    vf1[nr1] = y;
    urm1[nr1] = lst1[x];
    lst1[x] = nr1;
}

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

    nr2++;
    vf2[nr2] = y;
    urm2[nr2] = lst2[x];
    lst2[x] = nr2;
}

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

    nr3++;
    vf3[nr3] = y;
    urm3[nr3] = lst3[x];
    lst3[x] = nr3;
}

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

    viz1[x] = true;

    // PARCURG VECINII y AI LUI x

    p = lst1[x];

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

        if(!viz1[y]) dfs1(y);

        p = urm1[p];
    }

    C[++K] = x;
}

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

    viz2[x] = true;

    adauga_3(sol, x);

    // PARCURG VECINII y AI LUI x

    p = lst2[x];

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

        if(!viz2[y]) dfs2(y);

        p = urm2[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(!viz1[i]) dfs1(i);

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

            dfs2(C[i]);
        }

    out << sol << '\n';

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

        p = lst3[x];

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

            out << y << " ";

            p = urm3[p];
        }

        out << '\n';
    }

    return 0;
}