Cod sursa(job #2978257)

Utilizator alexandrubilaBila Alexandru-Mihai alexandrubila Data 13 februarie 2023 16:18:19
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
using namespace std;

const int NMAX = 100001;

int N, M, nrc;

vector <int> G[NMAX], GT[NMAX], CTC[NMAX], Post;
bool viz[NMAX];

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

void citire()
{
    int x, y;
    f >> N >> M;
    while (M--)
    {
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void dfs(int vf)
{
    viz[vf] = 1; ///+
    for (const int &x : G[vf])
        if (viz[x] == 0)
            dfs(x);
    Post.push_back(vf);
}

void dfsGT(int vf)
{
    viz[vf] = 0;
    CTC[nrc].push_back(vf);
    for (const int &x : GT[vf])
        if (viz[x] == 1)
        dfsGT(x);
}

void componente()
{
    for (int i = 1 ; i <= N ; ++i)
        if (viz[i] == 0)
            dfs(i);
    //
    for (auto it = Post.rbegin() ; it != Post.rend() ; ++it)
        if (viz[*it] == 1)
    {
        nrc++;
        dfsGT(*it);
    }
}

void afisare()
{
    g << nrc << '\n';
    for (int i = 1 ; i <= nrc ; ++i)
    {
        for (const auto &x : CTC[i])
            g << x << ' ';
        g << ' \n';
    }
}


int main()
{
        citire();
        componente();
        afisare();
        f.close();
        g.close();
    return 0;
}