Cod sursa(job #2066883)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 15 noiembrie 2017 17:32:33
Problema Componente tare conexe Scor 100
Compilator cpp 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;
}