Cod sursa(job #3357992)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 22:42:27
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int NMAX = 100005;

class Graf {
public:
    int n, m;
    vector<int> adj[NMAX], adjT[NMAX];

    void citire() {
        ifstream fin("ctc.in");
        fin >> n >> m;
        for (int i = 1; i <= m; i++) {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
            adjT[y].push_back(x);
        }
        fin.close();
    }

    void dfs1(int nod, vector<bool>& viz) {
        viz[nod] = true;
        for (int i : adj[nod]) {
            if (!viz[i]) {
                dfs1(i, viz);
            }
        }
    }

    void dfs2(int nod, vector<bool>& viz, vector<int>& ord) {
        viz[nod] = true;
        for (int i : adjT[nod]) {
            if (!viz[i]) {
                dfs2(i, viz, ord);
            }
        }
        ord.push_back(nod);
    }

    void kosaraju() {
        vector<bool> viz(n + 1, false);
        vector<int> ord;
        for (int i = 1; i <= n; i++) {
            if (!viz[i]) {
                dfs2(i, viz, ord);
            }
        }

        fill(viz.begin(), viz.end(), false);

        stack<int> st;
        int nr = 0;
        for (int i = ord.size() - 1; i >= 0; i--) {
            if (!viz[ord[i]]) {
                nr++;
                st.push(ord[i]);
                dfs1(ord[i], viz);
                while (!st.empty()) {
                    int nod = st.top();
                    st.pop();
                    cout << nod << " ";
                }
                cout << endl;
            }
        }
        cout << nr << endl;
    }
};

int main() {
    Graf g;
    g.citire();
    g.kosaraju();
    return 0;
}