Cod sursa(job #2723229)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 13 martie 2021 19:38:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 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;
bool Sel[NMAX];

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

vector < int > S;

vector < int > _temp;
vector < vector < int > > Sol;

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_1 (int Node)
{
    Sel[Node] = 1;

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

    S.push_back(Node);

    return;
}

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

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

    return;
}

static inline void DFS_2 (int Node)
{
    Sel[Node] = 1, _temp.push_back(Node);

    for(auto it : T[Node])
        if(!Sel[it])
            DFS_2(it);

    return;
}

static inline void Solve ()
{
    TopoSort();

    for(int i = 1; i <= N; ++i)
        Sel[i] = 0;

    for(auto it : S)
        if(!Sel[it])
        {
            _temp.clear();

            DFS_2(it);

            Sol.push_back(_temp);
        }

    g << (int)Sol.size() << '\n';

    for(auto it : Sol)
    {
        for(int j = 0; j < (int)it.size(); ++j)
        {
            g << it[j];

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

        g << '\n';
    }

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}