Cod sursa(job #3373623)

Utilizator Alexandru6041Alexandru Chelariu Alexandru6041 Data 7 noiembrie 2026 13:18:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <vector>
#include <algorithm>

int n, m, cnt;
std::vector < std::vector <int> > vecini, componente;
std::vector <int> viz, upperLimit;
std::vector < std::pair<int, int> > stivaMuchii; 

void getComponenta(int u, int w) {
    std::vector <int> comp;
    while(true) {
        auto e = stivaMuchii.back();
        stivaMuchii.pop_back();
        
        comp.push_back(e.first);
        comp.push_back(e.second);    

        if((e.first == u && e.second == w) || (e.first == w && e.second == u))
            break; ///break cand muchia este chiar w,u
    }

    sort(comp.begin(), comp.end());
    comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
    componente.push_back(comp);
}

void dfs(int u, int parinte) {
    upperLimit[u] = ++cnt;
    viz[u] = upperLimit[u];

    for(int w : vecini[u]) {
        if(w == parinte)
            continue;

        if(viz[w] == 0) {
            stivaMuchii.push_back({u, w});
            dfs(w, u);
            upperLimit[u] = std::min(upperLimit[u], upperLimit[w]);

            if(upperLimit[w] >= viz[u])
                getComponenta(u, w);
        } else if(viz[w] < viz[u]) {
            stivaMuchii.push_back({u, w});
            upperLimit[u] = std::min(upperLimit[u], viz[w]);
        }
    }
}

int main() {
    std::ifstream in("biconex.in");

    in >> n >> m;
    vecini.assign(n + 1, {});
    for(int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;

        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
    in.close();
    
    viz.assign(n + 1, 0);
    upperLimit.assign(n + 1, 0);

    for(int s = 1; s <= n; s++) {
        if(viz[s] == 0)
            dfs(s, 0);
    }

    std::ofstream out("biconex.out");
    out << (int) componente.size() << '\n';

    for(auto &c : componente)
        for(size_t i = 0; i < c.size(); i++)
            out << c[i] << (i + 1 < c.size() ? ' ' : '\n');

    out.close();
    return 0;
}