Cod sursa(job #3373397)

Utilizator ungureanubogdanUngureanu Bogdan ungureanubogdan Data 6 noiembrie 2026 20:21:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <stack>

std::ifstream cin("biconex.in");
std::ofstream cout("biconex.out");

int n, m;
std::vector<int> G[100001];
int nivel[100001];
int nma[100001];
int viz[100001];
std::stack<std::pair<int,int>> s;
std::vector<std::set<int>> cc;

void dfs(int nod, int tata = 0) {
    viz[nod] = 1;
    nivel[nod] = nivel[tata] + 1;
    nma[nod] = nivel[nod];

    for(auto nodnou : G[nod]) {
        if(nodnou != tata) {
            if(!viz[nodnou]) { // muchie din arbore
                s.push({nod, nodnou});
                dfs(nodnou, nod);
                nma[nod] = std::min(nma[nod], nma[nodnou]);
                
                if(nma[nodnou] >= nivel[nod]) { // componenta biconexa
                    std::set<int> aux;
                    while(1) {
                        auto x = s.top();    
                        s.pop();
                        
                        aux.insert(x.first);
                        aux.insert(x.second);
                        if(x.first == nod && x.second == nodnou) break;
                    }
                    cc.push_back(aux);
                }
            }
            else if (nivel[nodnou] < nivel[nod] ) { // muchie de intoarcere
                nma[nod] = std::min(nma[nod], nivel[nodnou]);
                s.push({nod, nodnou});
            }
        }    
    }
}

int main() {
    
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i) nma[i] = 2e9;
    for(int i = 1; i <= n; ++i) {
        if(!viz[i]) {
            nivel[i] = nma[i] = 1;
            dfs(i, 0);
        }
    }

    cout << cc.size() << '\n';
    for(auto v : cc) {
        for(auto x : v) {
            cout << x << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}