Cod sursa(job #1638033)

Utilizator daGramaGrama Matei daGrama Data 7 martie 2016 20:42:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 100003;
const int M = 200003;

int nr1, nr2, nr3, n, m, nc, c[N], nrc;
int lst1[N], vf1[M], urm1[M];
int lst2[N], vf2[M], urm2[M];
bool viz1[N], viz2[N], ok;
int lst3[N], vf3[M], urm3[M];


void adauga1( int x, int y )
{
    nr1++;
    vf1[nr1] = y;
    urm1[nr1] = lst1[x];
    lst1[x] = nr1;
}

void adauga2( int x, int y )
{
    nr2++;
    vf2[nr2] = y;
    urm2[nr2] = lst2[x];
    lst2[x] = nr2;
}

void adauga3( int x, int y )
{
    nr3++;
    vf3[nr3] = y;
    urm3[nr3] = lst3[x];
    lst3[x] = nr3;
}

void dfs1( int x )
{
    int y, p;
    viz1[x] = true;
    p = lst1[x];

    while( p != 0 )
    {
        y = vf1[p];
        if ( viz1[y] == false )
        {
            //viz1[y] = true;
            dfs1(y);
        }
        p = urm1[p];
    }
    c[++nc] = x;
}

void dfs2( int x )
{
    int y, p;
    p = lst2[x];
    viz2[x] = true;
    while( p != 0 )
    {
        y = vf2[p];
        if ( viz2[y] == false )
        {
            dfs2(y);
        }
        p = urm2[p];
    }
    adauga3(nrc, x);
    //out << x<<' ';
}

void afisare( int x )
{
    int p = lst3[x], y;
    while( p != 0 )
    {
        out << vf3[p]<<' ';
        p = urm3[p];
    }
    out <<'\n';
}

int main()
{
    int i, x, y;
    in >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        in >> x >> y;
        adauga1(x, y);
        adauga2(y, x);
    }

    for ( i = 1; i <= n; i++ )
        if ( viz1[i] == false )
        {
            dfs1(i);
        }


    for ( i = nc; i >= 1; i-- )
    {
        if ( viz2[ c[i] ] == false )
        {
            nrc++;
            dfs2(c[i]);
        }
    }
    out << nrc<<'\n';
    for ( i = 1; i <= nrc; i++ )
    {
        afisare(i);
    }
    return 0;
}