Cod sursa(job #1662416)

Utilizator filip.dutescuDutescu Filip Ioan filip.dutescu Data 24 martie 2016 19:09:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

const int N = 100005;
int n, m, x, y, nr=0, nrc=0;
int urm[2*N], vf[2*N], lst[N], urmt[N*2], vft[N*2], lstt[N*2], vfc[N*2], urmc[N*2], lstc[N*2], c[N];
bool viz[N];

void Adaugatc(int nc, int x)
{
    nrc++;
    vfc[nrc] = x;
    urmc[nrc] = lstc[nc];
    lstc[nc] = nrc;
}

void Adauga(int x, int y)
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;

    vft[nr] = x;
    urmt[nr] = lstt[y];
    lstt[y] = nr;
}

void dfst(int x)
{
    //out << x << " ";
    viz[x] = true;
    int p, y;
    p = lstt[x];
    Adaugatc(nr, x);

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

        if(!viz[y])
            dfst(y);

        p = urmt[p];
    }
}

void dfs(int x)
{
    viz[x] = true;
    int p, y;
    p = lst[x];

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

        if(!viz[y])
            dfs(y);

        p = urm[p];
    }
    c[++nr]=x;
}

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

    nr = 0;
    for(int i = 1; i <= n; i++)
    {
        if(!viz[i])
            dfs(i);
    }

    for(int i = 1; i <= n; i++)
    {
        viz[i] = false;
    }

    nr = nrc = 0;
    for(int i = n; i >= 1; i--)
    {
        if(!viz[c[i]])
        {
            nr++;
            dfst(c[i]);
            //out << "\n";
        }
    }

    out<<nr<<"\n";
    int p;
    for(int i = 1; i <= nr; i++)
    {
        p = lstc[i];

        while(p != 0)
        {
            x = vfc[p];
            out<<x<<' ';
            p = urmc[p];
        }
        out<<"\n";
    }
    return 0;
}