Cod sursa(job #3335619)

Utilizator ThatScode24Mihai Focsa ThatScode24 Data 23 ianuarie 2026 05:31:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <stack>
#include <vector>


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


class Graph {
private:
    int V;
    std::vector<std::vector<int>>adj;
    std::vector<std::vector<int>>adjT;

    std::vector<bool>viz;
    std::vector<bool>vizT;
    std::stack<int>st;
public:
    Graph(int n) {
        V = n;
        adj.resize(V+1); adjT.resize(V+1);
        viz.resize(V+1, false); vizT.resize(V+1, false);

    }

    void addEdge(int x, int y) {
        adj[x].push_back(y);
        adjT[y].push_back(x);
    }

    void dfs(int s) {
        viz[s] = true;
        for(const int& v : adj[s]) {
            if(!viz[v]) dfs(v);
        }
        st.push(s);
    }

    void dfsT(int s, std::vector<int>&mmb) {
        vizT[s] = true;
        mmb.push_back(s);
        for(const int& v : adjT[s]) {
            if(!vizT[v]) dfsT(v, mmb);
        }
    }

    void kosaraju() {
        std::vector<std::vector<int>>cc;
        int ccc = 0;

        for(int i=1;i<=V;++i) {
            if(!viz[i]) dfs(i);
        }

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


            if(!vizT[c]) {
                std::vector<int>curenta;
                ccc++;
                dfsT(c, curenta);
                cc.push_back(curenta);
            }
        }

        fout<<ccc<<std::endl;

        for(const std::vector<int> &c : cc) {
            for(int i=0;i<c.size();++i) {
                fout<< c[i] << " ";
            }
            fout<<std::endl;
        }
    }
};



int main(void) {
    int n, m, x, y;

    fin >> n >> m;
    Graph g(n);

    for(int i=1;i<=m;++i) {
        fin >> x >> y;
        g.addEdge(x, y);
    }

    g.kosaraju();

    return 0;
}