Cod sursa(job #1357283)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 23 februarie 2015 20:57:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>

using namespace std;

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

const int N = 100001, M = 200001;

int vf1[M], urm1[M], lst1[N], nr1 = 0;
int sortat[N], nr = 0;
int vf2[M], urm2[M], lst2[N], nr2 = 0;
bool ok[N];
int rez[2 * N];

int n, m;

void dfs_sortare(int x)
{
    ok[x] = 1;

    int p, y;
    p = lst1[x];

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

        if(!ok[y])
            dfs_sortare(y);

        p = urm1[p];
    }

    sortat[++nr] = x;
}

void dfs_invers(int x)
{
    rez[++nr] = x;
    ok[x] = 1;

    int y, p;
    p = lst2[x];

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

        if(!ok[y])
            dfs_invers(y);

        p = urm2[p];
    }
}

void citire()
{
    in >> n >> m;

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

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

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

int main()
{
    citire();

    for(int i = 1; i <= n; i++)
        if(!ok[i])
            dfs_sortare(i);

    for(int i = 1; i <= n; i++)
        ok[i] = 0;

    nr = 0;
    int counter = 0;
    for(int i = n; i >= 1; i--)
        if(!ok[sortat[i]])
        {
            counter++;
            dfs_invers(sortat[i]);
            rez[++nr] = -1;
        }

    out << counter << '\n';

    for(int i = 1; i <= nr; i++)
    {
        if(rez[i] == -1)
            out << '\n';
        else
            out << rez[i] << ' ';
    }
    return 0;
}