Cod sursa(job #3372496)

Utilizator mrvalentynTime Limit Exceeded mrvalentyn Data 4 noiembrie 2026 08:10:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long


const string FILENAME = "biconex";
ifstream f(FILENAME + ".in");
ofstream g(FILENAME + ".out");

#ifndef dg
#define cin f
#define cout g 
#endif

vector<int> gg[100001];

int vz[100001];

// niv = niv in arb dfs
// nma = niv minim accesibil la care se poate ajunge din k
//      mergand numai pe muchii de arbore si folosind ca ultima
//      muchie o muchie de intoarcere
// nma[k] = min(niv[k], min{niv[t], t legat de k}, 
//              min{niv[u], u fiu al lui k in arb dfs})

int niv [100001];
int nma[100001];

vector<vector<int>> ans;

stack<int> stk;

void dfs(int start, int p) {
    
    vz[start] = 1;
    stk.push(start);
    
    niv[start] = niv[p] + 1;
    nma[start] = niv[start];

    for(auto node : gg[start]) {
        if(node != p) {
            if(vz[node]){
                nma[start] = min(nma[start], niv[node]);
            }
            else {
                dfs(node,start);
                nma[start] = min(nma[start], nma[node]);

                // comp bco
                vector<int> comp;
                if(niv[start] <= nma[node]) {
                    while(stk.top() != node) {
                        comp.push_back(stk.top());
                        stk.pop();
                    }
                    comp.push_back(node);
                    stk.pop();
                    comp.push_back(start);

                    ans.push_back(comp);
                }
            }
        }
    }

}


signed main() {    

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

    for(int i=1;i<=n;++i) {
        if(!vz[i]){
            dfs(i,0);
        }

    }
    cout << ans.size() << '\n';
    for(auto &cmp : ans) {
        for(auto &x : cmp) cout << x << ' ';
        cout << '\n';
    }

    return 0;
}