Cod sursa(job #2393059)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 30 martie 2019 19:08:11
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 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);
}

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(1);

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

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

        if(Use[Nod])
            C[Use[Nod]].push_back(Nod);
        else
        {
            C[++Ans].push_back(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;
}