Cod sursa(job #3294784)

Utilizator 700_or_disbandBest team 700_or_disband Data 28 aprilie 2025 13:08:46
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
#define aaa system("read -r -p \"Press enter to continue...\" key");
#define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)std::cerr<<x[_]<<' ';std::cerr<<'\n',aaa
#define dbgs(x) std::cerr<<(#x)<<"[stl]: ";for(auto _:x)std::cerr<<_<<' ';std::cerr<<'\n',aaa
#define dbgp(x) std::cerr<<(#x)<<": "<<x.first<<' '<<x.second<<'\n',aaa
#define dbgsp(x) std::cerr<<(#x)<<"[stl pair]:\n";for(auto _:x)std::cerr<<_.first<<' '<<_.second<<'\n';aaa

const int maxn = 100'000;

std::vector<int> g[maxn+1];
int lvl[maxn+1], low[maxn+1];
std::vector<std::vector<int>> ctcs;
std::stack<int> low_stk;
bool viz[maxn+1], on_low_stk[maxn+1];

int tstamp;

void dfs(int nod, int t) {
    viz[nod] = true;
    lvl[nod] = 1 + lvl[t]; //but why?
    low[nod] = nod;
    low_stk.push(nod);
    on_low_stk[nod] = true;

    for (int nn: g[nod]) {
        ///nn trebuie sa nu fie deja rezolvat intr-un CTC, e.g. diamant cu 4 noduri, fara ciclu (1 2, 1 3, 3 4, 4 2).
        if (!viz[nn]) dfs(nn, nod);
        if (on_low_stk[nn] && lvl[low[nn]] < lvl[low[nod]]) low[nod] = low[nn];
    }

    if (low[nod] == nod) {
        ctcs.push_back(std::vector<int>());

        int top;
        do {
            top = low_stk.top();
            on_low_stk[top] = false;
            low_stk.pop();
            ctcs.back().push_back(top);
        } while (top != nod);
    }
}

int main() {
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");

    int n, m; fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b; fin >> a >> b;
        g[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        if (!viz[i]) dfs(i, 0);
    }

    fout << ctcs.size() << '\n';
    for (const auto &ctc: ctcs) {
        for (int z: ctc) fout << z << ' ';
        fout << '\n';
    }

    return 0;
}