Cod sursa(job #3294613)

Utilizator _andr31Rusanescu Andrei-Marian _andr31 Data 26 aprilie 2025 16:06:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;

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

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

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

    vector<int> low_link(n + 1, INT_MAX), index(n + 1, -1);
    vector<bool> in_stack(n + 1);
    stack<int> st;
    int t = 0;
    vector<vector<int>> ctcs;
    function<void(int)> dfs = [&](int nod) -> void {
        low_link[nod] = index[nod] = ++t;
        st.push(nod);
        in_stack[nod] = true;
        for (int vec : adj[nod]) {
            if (index[vec] == -1) {
                dfs(vec);
                low_link[nod] = min(low_link[nod], low_link[vec]);
            } else if (in_stack[vec]) {
                low_link[nod] = min(low_link[nod], index[vec]);
            }
        }
        if (low_link[nod] == index[nod]) {
            int x;
            vector<int> ctc;
            do {
                x = st.top(); st.pop();
                ctc.push_back(x);
                in_stack[x] = false;
            } while (x != nod);
            ctcs.push_back(ctc);
        }
    };
    for (int i = 1; i <= n; ++i) {
        if (index[i] == -1) {
            dfs(i);
        }
    }

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

    return 0;
}