Cod sursa(job #3374209)

Utilizator ryuuAdrian Rusu ryuu Data 8 noiembrie 2026 20:30:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int main() {
    int n, m;
    fin >> n >> m;

    vector<vector<int> > g(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
    }

    vector<int> idx(n + 1, 0), low(n + 1, 0), it(n + 1, 0);
    vector<char> onStack(n + 1, 0);
    vector<int> stk, call;
    vector<vector<int> > comps;
    int timer = 0;

    for (int s = 1; s <= n; s++) {
        if (idx[s]) continue;

        // DFS iterativ (evita depasirea stivei la N = 100000)
        idx[s] = low[s] = ++timer;
        stk.push_back(s);
        onStack[s] = 1;
        call.push_back(s);

        while (!call.empty()) {
            int u = call.back();

            if (it[u] < (int)g[u].size()) {
                int v = g[u][it[u]++];
                if (!idx[v]) {
                    idx[v] = low[v] = ++timer;
                    stk.push_back(v);
                    onStack[v] = 1;
                    call.push_back(v);
                } else if (onStack[v]) {
                    low[u] = min(low[u], idx[v]);
                }
            } else {
                // am terminat de explorat u
                if (low[u] == idx[u]) {
                    comps.push_back(vector<int>());
                    int w;
                    do {
                        w = stk.back();
                        stk.pop_back();
                        onStack[w] = 0;
                        comps.back().push_back(w);
                    } while (w != u);
                }
                call.pop_back();
                if (!call.empty()) {
                    int p = call.back();
                    low[p] = min(low[p], low[u]);
                }
            }
        }
    }

    fout << comps.size() << "\n";
    for (int i = 0; i < (int)comps.size(); i++) {
        for (int j = 0; j < (int)comps[i].size(); j++)
            fout << comps[i][j] << " ";
        fout << "\n";
    }
    return 0;
}