Cod sursa(job #3319723)

Utilizator iuliarusuIulia Rusu iuliarusu Data 2 noiembrie 2025 20:53:19
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;
vector<int> L[100001];
stack<pair<int,int>> st;
vector<vector<int>> biconexe;
int niv[100001], low[100001];
ifstream f("biconex.in");
ofstream g("biconex.out");

void DFS(int nod, int parent) {
    int nr = 0;
    niv[nod] = niv[parent] + 1;
    low[nod] = niv[nod];
    for (int vecin: L[nod]) {
        if (vecin == parent) continue;
        if (niv[vecin]) {
            low[nod] = min(low[nod], niv[vecin]);
        }
        else {
            st.push({nod,vecin});
            nr++;
            DFS(vecin, nod);
            low[nod] = min(low[nod], low[vecin]);

            if (parent != -1 && low[vecin] >= niv[nod]
                || parent == -1 && nr >= 2) {
                vector<int> c;
                pair <int,int> muchii;
                do {
                    muchii = st.top();
                    st.pop();
                    c.push_back(muchii.first);
                    c.push_back(muchii.second);
                }while (!(muchii.first == nod && muchii.second == vecin));
                c.erase(unique(c.begin(), c.end(), c.end()));
                biconexe.push_back(c);
            }
        }
    }
}
int main() {
    int n, m;
    f >> n >> m;
    for (int i=1; i<=m; i++) {
        int a, b;
        f >> a >> b;
        L[a].push_back(b);
        L[b].push_back(a);
    }
    queue<int> q;
    for (int i=1; i<=n;i++)
        if (!niv[i])
            DFS(i, -1);
    
    g << biconexe.size() << "\n";
    for (auto &c : biconexe) {
        for (int nod : c)
            g << nod << " ";
        g << "\n";
    }
    return 0;
}