Cod sursa(job #2792027)

Utilizator XeinIonel-Alexandru Culea Xein Data 31 octombrie 2021 18:09:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>

#define NMAX 100009

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

int N, M;
std::vector<int> Adiacenta[NMAX];
std::vector<int> t_Adiacenta[NMAX];  // Transpus
std::vector<std::vector<int>> compTC;
int stivaTopo[NMAX], stVf;
bool vizitat[NMAX];

void Dfs(int nod)
{
    vizitat[nod] = true;
    for (auto& vecin : Adiacenta[nod])
        if (!vizitat[vecin])
            Dfs(vecin);
    stivaTopo[++stVf] = nod; 
}

void t_Dfs(int nod)
{
    vizitat[nod] = true;
    for (auto& vecin : t_Adiacenta[nod])
        if (!vizitat[vecin])
            t_Dfs(vecin);
    compTC.back().push_back(nod);
}

int main()
{
    f >> N >> M;

    for (int x, y, i = 0; i < M; ++i)
    {
        f >> x >> y;
        Adiacenta[x].push_back(y);
        t_Adiacenta[y].push_back(x);
    }

    for (int nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            Dfs(nod);

    for (int nod = 1; nod <= N; ++nod)
        vizitat[nod] = false;
    while (stVf)
    {
        if (!vizitat[stivaTopo[stVf]])
        {
            compTC.push_back({});
            t_Dfs(stivaTopo[stVf]);
        }
        --stVf;
    }

    g << compTC.size() << '\n';
    for (auto& comp : compTC)
    {
        for (auto& nod : comp)
            g << nod << ' ';
        g << '\n';
    }

    return 0;
}