Cod sursa(job #3374963)

Utilizator merdanovylham03@gmail.comMerdanov Ylham [email protected] Data 9 noiembrie 2026 20:30:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int maxn = 100005;
vector<int> graf[maxn], invers[maxn], ordine;
bool viz[maxn];
int componenta[maxn];

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        graf[a].push_back(b);
        invers[b].push_back(a);
    }

    // Primul DFS: ordinea de terminare.
    vector<int> poz(n + 1, 0);
    for (int start = 1; start <= n; start++) {
        if (viz[start]) continue;
        stack<int> st;
        st.push(start);
        viz[start] = true;
        while (!st.empty()) {
            int u = st.top();
            if (poz[u] < (int)graf[u].size()) {
                int v = graf[u][poz[u]++];
                if (!viz[v]) {
                    viz[v] = true;
                    st.push(v);
                }
            } else {
                ordine.push_back(u);
                st.pop();
            }
        }
    }

    // Al doilea DFS: graful transpus.
    vector<vector<int>> raspuns;
    for (int i = (int)ordine.size() - 1; i >= 0; i--) {
        int start = ordine[i];
        if (componenta[start]) continue;
        int id = (int)raspuns.size() + 1;
        raspuns.push_back(vector<int>());
        stack<int> st;
        st.push(start);
        componenta[start] = id;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            raspuns.back().push_back(u);
            for (int v : invers[u]) {
                if (!componenta[v]) {
                    componenta[v] = id;
                    st.push(v);
                }
            }
        }
    }

    fout << raspuns.size() << '\n';
    for (auto comp : raspuns) {
        for (int u : comp) fout << u << ' ';
        fout << '\n';
    }
    return 0;
}