Cod sursa(job #2393075)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 30 martie 2019 19:28:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMax = 1e5;

int N, M, Use[NMax + 5], Ans;

vector <int> G[NMax + 5], ST, GT[NMax + 5], C[NMax + 5];

void DFSP(int Nod)
{
    Use[Nod] = 1;

    for(auto Vecin : G[Nod])
        if(Use[Vecin] == 0)
            DFSP(Vecin);

    ST.push_back(Nod);
}

void DFSM(int Nod, int c)
{
    Use[Nod] = c;

    for(auto Vecin : GT[Nod])
        if(Use[Vecin] == 0)
            DFSM(Vecin, c);

    C[c].push_back(Nod);
}

void Read()
{
    fin >> N >> M;

    for(int i = 1, x, y; i <= M; i++)
    {
        fin >> x >> y;

        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void Solve()
{
    for(int i = 1; i <= N; i++)
        if(Use[i] == 0)
            DFSP(i);

    memset(Use, 0, sizeof(Use));

    while(ST.size())
    {
        int Nod = ST.back(); ST.pop_back();

        if(!Use[Nod])
            DFSM(Nod, ++Ans);
    }
}

void Print()
{
    fout << Ans << '\n';

    for(int i = 1; i <= Ans; i++)
    {
        for(auto j : C[i])
            fout << j << " ";

        fout << '\n';
    }
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();

    return 0;
}