Cod sursa(job #3374495)

Utilizator Dani111Gheorghe Daniel Dani111 Data 9 noiembrie 2026 01:24:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000;
int N, M;
vector<int> G[MAX + 3];
int low[MAX + 3], lev[MAX + 3];
vector<int> st;
vector<int> ans[MAX + 3];
int k;

void dfs(int nod, int tata = 0) {
    lev[nod] = low[nod] = lev[tata] + 1;
    st.push_back(nod);

    for(auto i : G[nod]) {
        if(i == tata) continue;
        
        if(!lev[i]) {
            dfs(i, nod);
            low[nod] = min(low[nod], low[i]);
            
            if(low[i] >= lev[nod]) {
                k++;
                while(st.back() != i) {
                    ans[k].push_back(st.back());
                    st.pop_back();
                }
                ans[k].push_back(st.back());
                st.pop_back();
                ans[k].push_back(nod);
            }
        } else {
            low[nod] = min(low[nod], lev[i]);
        }
    }
}

int main() {
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    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++) {
        if(!lev[i]) dfs(i);
    }

    cout << k << '\n';
    for(int i = 1; i <= k; i++) {
        for(auto nod : ans[i]) {
            cout << nod << ' ';
        }
        cout << '\n';
    }

    return 0;
}