Cod sursa(job #2673909)

Utilizator KPP17Popescu Paul KPP17 Data 18 noiembrie 2020 09:47:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#define fisier "ctc"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int N = 100000;
#include <vector>
std::vector<int> L[N], S;
int LL[N], ID[N], nId;
#include <bitset>
std::bitset<N> E, pS;
std::vector<std::vector<int>> CTC;
void dfs(int t)
{
    pS[t] = true;
    ID[t] = LL[t] = nId++;
    S.push_back(t);
    for (int f: L[t])
        if (not E[f])
        {
            if (not pS[f])
                dfs(f);
            LL[t] = std::min(LL[t], LL[f]);
        }
    if (ID[t] == LL[t])
    {
        CTC.emplace_back();
        int back;
        do
        {
            back = S.back();
            S.pop_back();
            CTC.back().push_back(back);
            E[back] = true;
        }
        while (back != t);
    }
}
int main()
{
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int a, b;
        in >> a >> b;
        L[--a].push_back(--b);
    }
    for (int i = 0; i < n; i++)
        if (not E[i])
            dfs(i);
    out << CTC.size() << '\n';
    for (auto ctc: CTC)
    {
        for (int i: ctc)
            out << i + 1 << ' ';
        out << '\n';
    }
}