Cod sursa(job #3336332)

Utilizator 06cezarCiocirlan Cezar-Gabriel 06cezar Data 24 ianuarie 2026 16:18:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector<vector<int>> la;
vector<vector<int>> lat;
vector<vector<int>> ctc;
vector<bool> viz;
stack<int> st;
int c = 0;

void dfs1(int s) {
    viz[s] = true;
    for(int v : la[s]) {
        if(!viz[v]) dfs1(v);
    }
    st.push(s);
}

void dfs2(int s, vector<int> &compCurr) {
    viz[s] = true;
    compCurr.push_back(s);
    for(int v : lat[s]) {
        if(!viz[v]) dfs2(v, compCurr);
    }
}

int main() {
    int n, m, x, y;
    cin >> n >> m;
    la.assign(n + 1, {});
    lat.assign(n + 1, {});
    viz.assign(n + 1, 0);

    for(int i = 1; i <= m; i++) {
        cin >> x >> y;
        la[x].push_back(y);
        lat[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(!viz[i]) dfs1(i);

    viz.assign(n + 1, 0);

    while(!st.empty()) {
        int curr = st.top();
        st.pop();
        if(!viz[curr]) {
            vector<int> compCurr;
            dfs2(curr, compCurr);
            ctc.push_back(compCurr);
        }
    }

    cout << ctc.size() << endl;
    for(vector<int> vec : ctc) {
        for(int x : vec) {
            cout << x << ' ';
        }
        cout << endl;
    }
    return 0;
}