Cod sursa(job #3373930)

Utilizator TintsooTint Sabei Soe Win Tintsoo Data 8 noiembrie 2026 11:20:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream> 
#include <fstream> 
#include <vector> 
#include <stack> 
#include <algorithm> 

using namespace std; 

const int MAX = 100005;
int n, m; 
int timer; 
vector<int> adj[MAX]; 
int disc[MAX], low[MAX]; 
stack<pair<int,int>> st; 
vector<vector<int>> bcc; 

void biconex(int u, int p){

    disc[u] = low[u] = ++timer; 
    int children = 0; 

    for (int v : adj[u]){

        if (v == p) continue; 

        if (disc[v] == 0) {
            children++; 
            st.push({v, u}); 
            biconex(v, u); 
            low[u] = min(low[u], low[v]); 

            if (low[v] >= disc[u]){

                vector<int> comp; 
                pair<int, int> edge; 
                
                while (true){
                    edge = st.top();
                    st.pop(); 

                    comp.push_back(edge.first);
                    comp.push_back(edge.second);  

                    if (edge.first == v && edge.second == u) break; 

                }

                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end()); 

                bcc.push_back(comp);
            
            }

        }

        else if (disc[v] != 0){
            low[u] = min(low[u], disc[v]); 
        }
        
    }
}

int main(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out"); 

    fin >> n >> m; 

    for (int i = 0; i < m; i++){
        int u, v;
        fin >> u >> v; 

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++){
        if (disc[i] == 0){
            biconex(i, 0); 
        }
    }

    fout << bcc.size() << endl; 
    
    for (auto b : bcc){
        for (int i : b){
            fout << i << " "; 
        }

        fout << endl; 
    }

    return 0; 

}