Cod sursa(job #3357724)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 13:12:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m;
vector<vector<int> > gr(100100);
vector<vector<int> > inv(100100);
vector<bool> used(100100);
vector<bool> inStack(100100);
vector<int> disc(100100);
vector<int> low(100100);
stack<int> st;
vector<vector<int> > ans;
int timer = 0;

void dfs(int node) {
    used[node] = true;
    disc[node] = low[node] = ++timer;
    st.push(node);
    inStack[node] = true;

    for (auto &x : gr[node]) {
        if (!used[x]) {
            dfs(x);
            low[node] = min(low[node], low[x]);
        } else if (inStack[x]) {
            low[node] = min(low[node], disc[x]);
        }
    }

    if (low[node] == disc[node]) {
        vector<int> comp;
        int v;
        do {
            v = st.top();
            st.pop();
            inStack[v] = false;
            comp.push_back(v);
        } while (v != node);
        ans.push_back(comp);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        gr[a].push_back(b);
    }

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

    cout << ans.size() << '\n';

    for (auto &x : ans) {
        for (auto &y : x) {
            cout << y << " ";
        }
        cout << '\n';
    }

    return 0;
}