Cod sursa(job #3350355)

Utilizator marelucaMare Luca Ghita mareluca Data 7 aprilie 2026 12:53:37
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

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

const int NMAX = 100005;

bool onStack[NMAX];
int low[NMAX], disc[NMAX];
std::vector<int> graph[NMAX];
std::stack<int> st;
std::vector<std::vector<int>> sccs;

void compute_sccs(int from) {
    static int time = 0;
    low[from] = disc[from] = ++time;
    onStack[from] = true;
    st.push(from);

    for(int to : graph[from]) {
        if(!disc[to]) {
            compute_sccs(to);

            low[from] = std::min(low[from], low[to]);
        }
        else if(onStack[to]) {
            low[from] = std::min(low[from], low[to]);
        }
    }

    if(low[from] == disc[from]) {
        int top;
        std::vector<int> scc;

        do {
            top = st.top();
            st.pop();
            scc.push_back(top);
        } while(top != from);

        sccs.push_back(scc);
    }
}

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

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

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

    fout << sccs.size() << '\n';

    for(std::vector<int> scc : sccs) {
        for(int c : scc) {
            fout << c << ' ';
        }fout << '\n';
    }

    return 0;
}