Cod sursa(job #3373785)

Utilizator ztefanDenciu Stefan ztefan Data 7 noiembrie 2026 21:34:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.88 kb
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <fstream>

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

struct edge{
    int i,j;
    bool operator==(const edge& other) const {
        return (this->i == other.i && this->j == other.j) || 
               (this->i == other.j && this->j == other.i);
    }

    bool operator!=(const edge& other) const {
        return !(*this == other);
    }
};

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

    std::vector<bool> visited;
    std::vector<int> depth;
    std::vector<int> minimum_level;

    std::istream& input;
    std::ostream& output;

    std::vector<edge> critical_edges;

    std::stack<edge> edge_stack;

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

    void backpropagate_minimum_level(int shallower_node,int deeper_node){
        minimum_level[shallower_node] = std::min(minimum_level[shallower_node],minimum_level[deeper_node]);
    }

    bool is_direct_descendant(int deeper_node,int shallower_node){
        return depth[deeper_node] == depth[shallower_node]+1;
    }

    void update_returning_edge_minimum_level(int deeper_node,int shallower_node){
        minimum_level[deeper_node] = std::min(minimum_level[deeper_node],depth[shallower_node]);
    }

    bool is_child_in_lower_cycle(int shallower_node,int deeper_node){
        return minimum_level[deeper_node]>=depth[shallower_node];
    }

    void empty_stack(edge critical_edge){
        std::set<int> biconnected_component;
        edge curr_edge;
        do{
            curr_edge=edge_stack.top();
            edge_stack.pop();
            biconnected_component.insert(curr_edge.i);
            biconnected_component.insert(curr_edge.j);
        }while(curr_edge != critical_edge);
        biconnected_components.push_back(biconnected_component);
    }

    void dfs(int node){
        visited[node]=true;
        minimum_level[node]=depth[node];

        for(auto neighbour : edges[node]){
            if(!visited[neighbour]){
                depth[neighbour]=depth[node]+1;

                edge_stack.push({node,static_cast<int>(neighbour)});
                dfs(neighbour);

                backpropagate_minimum_level(node,neighbour);

                if(is_child_in_lower_cycle(node,neighbour)){
                    empty_stack({node,static_cast<int>(neighbour)});
                }
            }else{
                if(!is_direct_descendant(node,neighbour)){
                    update_returning_edge_minimum_level(node,neighbour);
                }
            }
        }
    }
public:
    Solution(std::istream& input,std::ostream& output) : input(input), output(output){}
    void read(){
        input>>node_count>>edge_count;
        edges.resize(node_count+1);

        visited.resize(node_count+1,false);
        depth.resize(node_count+1,-1);
        minimum_level.resize(node_count+1,-1);
        auto read_edge=[&](){
            int node1,node2;
            input>>node1>>node2;
            edges[node1].push_back(node2);
            edges[node2].push_back(node1);
        };
        iterate(edge_count,read_edge);
    }
    void run(){
        constexpr int initial_node=1;
        visited[initial_node]=true;
        depth[initial_node]=1;
        dfs(initial_node);
    }
    void print(){

        output<<biconnected_components.size()<<"\n";

        for(auto biconnected_component:biconnected_components){
            for(auto node:biconnected_component){
                output<<node<<" ";
            }
            output<<"\n";
        }
    }
};

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