Cod sursa(job #3372096)

Utilizator EmimaCurcan Sara Emima Emima Data 2 noiembrie 2026 14:55:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

void dfsG(int nod, const vector<vector<int>>& graf, vector<int>& viz, stack<int>& st) {
    viz[nod] = 1;
    for (int vecin : graf[nod])
        if (viz[vecin]==0)
            dfsG(vecin, graf, viz, st);
    st.push(nod);
}

vector<vector<int>> grafT(int n, const vector<vector<int>>& graf) {
    vector<vector<int>> transpus(n + 1);
    for (int i=1;i<=n;++i)
        for (int vecin : graf[i])
            transpus[vecin].push_back(i);
    return transpus;
}

void dfsT(int nod, const vector<vector<int>>& transpus, vector<int>& viz, vector<int>& comp) {
    viz[nod] = 2;
    comp.push_back(nod);
    for (int vecin : transpus[nod])
        if (viz[vecin]!=2)
            dfsT(vecin, transpus, viz, comp);
}

int main() {
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m;

    f>>n>>m;

    vector<vector<int>> graf(n+1);
    for (int i=0;i<m;++i) {
        int u,v;
        f>>u>>v;
        graf[u].push_back(v);
    }

    vector<int> viz(n+1, 0);
    stack<int> st;

    for (int i=1;i<=n;++i) {
        if (viz[i]==0)
            dfsG(i, graf, viz, st);
    }

    vector<vector<int>> transpus = grafT(n, graf);
    vector<vector<int>> ctc;

    while (!st.empty()) {
        int nod = st.top();
        st.pop();

        if (viz[nod]!=2) {
            vector<int> comp;
            dfsT(nod,transpus,viz,comp);
            ctc.push_back(comp);
        }
    }

    g << ctc.size() << "\n";
    for (const auto& comp : ctc) {
        for (int nod : comp)
            g<<nod<<" ";
        g<< "\n";
    }

    f.close();
    g.close();
    return 0;
}