Cod sursa(job #3337252)

Utilizator ThatScode24Mihai Focsa ThatScode24 Data 27 ianuarie 2026 07:54:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

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


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

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, std::stack<int>& st) {
        viz[s] = true;
        for(auto& v : adj[s]) {
            if(!viz[v]) {
                dfs(v, st);
            }
        }
        st.push(s);
    }

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

    void proc() {
        std::stack<int>st;
        std::vector<std::vector<int>>cc;
        for(int i=1;i<=V;++i) {
            if(!viz[i]) {
                dfs(i, st);
            }
        }
        int counter = 0;
        while(!st.empty()) {
            int c = st.top();
            st.pop();
            if(!vizT[c]) {
                counter++;
                std::vector<int>comp;
                dfsT(c, comp);
                cc.push_back(comp);
            }
        }
        fout<<counter<<'\n';
        for(auto& elem : cc) {
            for(auto& e : elem) {
                fout<<e<<' ';
            }
            fout<<'\n';
        }
    }
};



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.proc();
    return 0;
}