Cod sursa(job #2738591)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 6 aprilie 2021 09:09:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 1e5 + 1;

int N, M;
vector < int > G[NMAX], T[NMAX];

bool Sel[NMAX];
vector < int > V;

vector < int > Sol[NMAX];

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int X = 0, Y = 0;
        f >> X >> Y;

        G[X].push_back(Y), T[Y].push_back(X);
    }

    return;
}

static inline void DFS (int Node)
{
    Sel[Node] = 1;

    for(auto it : G[Node])
        if(!Sel[it])
            DFS(it);

    V.push_back(Node);

    return;
}

static inline void TopoSort ()
{
    for(int i = 1; i <= N; ++i)
        if(!Sel[i])
            DFS(i);

    reverse(V.begin(), V.end());

    return;
}

static inline void Reset ()
{
    for(int i = 1; i <= N; ++i)
        Sel[i] = 0;

    return;
}

static inline void Go (int Node, int Id)
{
    Sel[Node] = 1;
    Sol[Id].push_back(Node);

    for(auto it : T[Node])
        if(!Sel[it])
            Go(it, Id);

    return;
}

static inline void Solve ()
{
    Reset();

    int cnt = 0;

    for(auto it : V)
        if(!Sel[it])
            Go(it, ++cnt);

    g << cnt << '\n';

    for(int i = 1; i <= cnt; ++i)
    {
        for(int j = 0; j < (int)Sol[i].size(); ++j)
        {
            g << Sol[i][j];

            if(j != (int)Sol[i].size() - 1)
                g << ' ';
        }

        g << '\n';
    }

    return;
}

int main ()
{
    Read();

    TopoSort();

    Solve();

    return 0;
}