Cod sursa(job #3334158)

Utilizator tudorbeloiuLuka Modric tudorbeloiu Data 16 ianuarie 2026 16:34:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>


using namespace std;


ifstream f("biconex.in");
ofstream g("biconex.out");

const int INF = 1e8;

int n,m,x,y;
vector<vector<int>> adj;
vector<int> visited;
vector<int> nivel;
vector<int> niv_min;
stack<pair<int,int>> st;

vector<vector<int>> rez;


void critic(int nod,int tata){

    visited[nod] = 1;
    niv_min[nod] = nivel[nod];

    for(auto& neigh: adj[nod]){

        if(visited[neigh] == 0){
            st.push({nod,neigh});
            nivel[neigh] = nivel[nod] + 1;

            critic(neigh,nod);

            niv_min[nod] = min(niv_min[neigh], niv_min[nod]);

            if(niv_min[neigh] >= nivel[nod]){ //critical node condition (>=)  | critical edge condition (>)
                set<int> componenta_conexa;
                while(true){
                    pair<int,int> muchie = st.top();
                    st.pop();

                    componenta_conexa.insert(muchie.first);
                    componenta_conexa.insert(muchie.second);

                    if(muchie.first == nod && muchie.second == neigh)
                        break;
                    if(muchie.first == neigh && muchie.second == nod)
                        break;
                }
                vector<int> comp(componenta_conexa.begin(), componenta_conexa.end());
                rez.push_back(comp);
            }

        }
        else{
            if(tata!=neigh && nivel[neigh] < nivel[nod]){
                st.push({nod,neigh});
                niv_min[nod] = min(niv_min[nod], nivel[neigh]);
            }
        }
    }
    
}

int main(){
    f >> n >> m;

    adj.resize(n+1);
    visited.assign(n+1, 0);
    nivel.assign(n+1, 0);
    niv_min.assign(n+1, 0);

    for(int i=1; i<=m; i++){
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    nivel[1] = 1;
    critic(1,-1);
    
    g << rez.size() << '\n';
    for(int i=0; i<rez.size(); i++){
        int n=rez[i].size();
        for(int j=0; j<n; j++){
            g << rez[i][j] << " "; 
        }
        g << '\n';
    }

    return 0;
}