Cod sursa(job #3373829)

Utilizator ztefanDenciu Stefan ztefan Data 7 noiembrie 2026 22:43:14
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <fstream>

template <typename T>
void iterate(int count,T lambda){
    for(int i=0;i<count;i++){
        lambda();
    }
}

class Solution{
    int node_count,edge_count;
    std::vector<std::vector<int>> edges;
    std::vector<bool> visited;

    std::istream& input;
    std::ostream& output;
    std::stack<int> exit_stack;

    std::vector<std::set<int>> strong_connected_components;


    void dfs1(int node){
        for(auto neighbour:edges[node]){
            if(visited[neighbour]){
                continue;
            }
            visited[neighbour]=true;
            dfs1(neighbour);
        }
        exit_stack.push(node);
    }

    void transpose(){
        std::vector<std::vector<int>> transposed_edges;
        transposed_edges.resize(node_count+1);
        for(int node=1;node<=node_count;node++){
            for(auto neighbour:edges[node]){
                transposed_edges[neighbour].push_back(node);
            }
        }
        edges.clear();
        edges=transposed_edges;
    }

    void dfs2(int node){
        for(auto neighbour:edges[node]){
            if(visited[neighbour]){
                continue;
            }
            visited[neighbour]=true;
            dfs2(neighbour);
        }
    }

    void add_component(){
        strong_connected_components.push_back({});
    }

    void add_node(int node){
        strong_connected_components.back().insert(node);
    }

    void first_pass(){
        visited.clear();
        visited.resize(node_count+1,false);
        for(int node=1;node<=node_count;node++){
            if(!visited[node]){
                visited[node]=true;
                dfs1(node);
            }
        }
    }

    void second_pass(){
        visited.clear();
        visited.resize(node_count+1,false);
        while(!exit_stack.empty()){
            int node=exit_stack.top();
            if((int)visited[node]){
                add_node(node);
                exit_stack.pop();
                continue;
            }
            add_component();
            add_node(node);
            dfs2(node);
            exit_stack.pop();
        }
    }

public:
    Solution(std::istream& input,std::ostream& output) : input(input), output(output){}
    void read(){
        input>>node_count>>edge_count;
        edges.resize(node_count+1);

        auto read_edge=[&](){
            int node1,node2;
            input>>node1>>node2;
            edges[node1].push_back(node2);
        };
        iterate(edge_count,read_edge);
    }
    void run(){
        first_pass();
        transpose();
        second_pass();
    }
    void print(){
        for(auto strong_connected_component:strong_connected_components){
            for(auto node:strong_connected_component){
                output<<node<<" ";
            }
            output<<"\n";
        }
    }
};

int main(){
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");
    Solution ctc(fin,fout);
    ctc.read();
    ctc.run();
    ctc.print();
}