Cod sursa(job #2298378)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 8 decembrie 2018 09:25:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>

#include <vector>



using namespace std;



ifstream in("ctc.in");

ofstream out("ctc.out");



int N, M;



vector <int> orig[100005], transp[100005], sol[100005];



int temp[100005], k;



bool viz[100005];



int counter;



void Read()

{

    in >> N >> M;



    for(int i = 1; i <= M; i++)

    {

        int x, y;

        in >> x >> y;



        orig[x].push_back(y);

        transp[y].push_back(x);

    }

}



void DFP(int node)

{

    viz[node] = 1;



    for(int i = 0; i < orig[node].size(); i++)

    {

        int v = orig[node][i];

        if(viz[v] == 0)

            DFP(v);

    }



    temp[++k] = node;

}



void DFM(int node)

{

    viz[node] = 0;



    sol[counter].push_back(node);



    for(int i = 0; i < transp[node].size(); i++)

    {

        int v = transp[node][i];

        if(viz[v] == 1)

            DFM(v);

    }

}



void Kosaraju()

{

    for(int i = 1; i <= N; i++)

        if(viz[i] == 0)

            DFP(i);



    for(int i = k; i >= 1; i--)

    {

        if(viz[temp[i]] == 1)

        {

            counter ++;

            DFM(temp[i]);

        }

    }



    out << counter << "\n";



    for(int i = 1; i <= counter; i++)

    {

        for(int j = 0; j < sol[i].size(); j++)

            out << sol[i][j] << " ";

        out << "\n";

    }

}

int main()

{

    Read();

    Kosaraju();

    return 0;

}