Cod sursa(job #2870705)

Utilizator servus2022Stefan Tonut servus2022 Data 12 martie 2022 15:13:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

typedef vector < int > VI;

const int NMAX = 1e5 + 1;

int N;
VI G[NMAX], GT[NMAX];

bool Sel[NMAX];

VI List;

VI _temp;
vector < VI > Sol;

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

    f >> N;

    int M = 0;
    f >> M;

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

        G[u].push_back(v), GT[v].push_back(u);
    }

    return;
}

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

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

    List.push_back(Node);

    return;
}

static inline void Go (int Node)
{
    Sel[Node] = 0;

    _temp.push_back(Node);

    for(auto it : GT[Node])
        if(Sel[it])
            Go(it);

    return;
}

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

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

    for(auto it : List)
        if(Sel[it])
            _temp.clear(), Go(it), Sol.push_back(_temp);

    return;
}

static inline void Write ()
{
    g << (int)Sol.size() << '\n';

    for(auto i : Sol)
    {
        sort(i.begin(), i.end());

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

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

        g << '\n';
    }

    return;
}

int main()
{
    Read();

    Solve();

    Write();

    return 0;
}