Cod sursa(job #3332396)

Utilizator coco11coraline kalbfleisch coco11 Data 6 ianuarie 2026 15:38:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
vector<int> adj[MAXN+1];
int disc[MAXN+1], low[MAXN+1], timer;
stack<pair<int,int>> st;
vector<vector<int>> bcc;

void dfs(int u, int p) {
    disc[u] = low[u] = ++timer;
    for (int v : adj[u]) {
        if (!disc[v]) {
            st.push({u,v});
            dfs(v,u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) {
                vector<int> comp;
                while (!st.empty()) {
                    auto e = st.top(); st.pop();
                    comp.push_back(e.first);
                    comp.push_back(e.second);
                    if (e.first == u && e.second == v) break;
                }
                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                bcc.push_back(comp);
            }
        } else if (v != p && disc[v] < disc[u]) {
            st.push({u,v});
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n,m;
    fin >> n >> m;
    for (int i=0;i<m;i++) {
        int x,y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i=1;i<=n;i++) if (!disc[i]) dfs(i,-1);
    fout << bcc.size() << "\n";
    for (auto &comp : bcc) {
        for (int v : comp) fout << v << " ";
        fout << "\n";
    }
    return 0;
}