Cod sursa(job #2982114)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 19 februarie 2023 16:29:41
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
const int nmx = 1e5 + 4;
vector<int> ad[nmx];
int low[nmx],h[nmx],vis[nmx];
int nc[nmx];
vector<vector<int>> cxx={{}};
#if 1
#define cin fin
#define cout fout
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#endif // 1
vector<int> stk;
void dfs(int k,int t){
    stk.push_back(t);
    stk.push_back(k);
    int nrfi = 0;
    vis[k] = 1;
    h[k] = h[t] + 1;
    low[k] = h[k];
    for(int to : ad[k]){
        if(vis[to] == 0){
            nrfi++;
            dfs(to,k);
            low[k] = min(low[k],low[to]);
            if(low[to]>=h[k]){
                nc[k] = 1;
                while(stk.back()!=k){
                    if(cxx.back().size())
                        if(cxx.back().back()==stk.back())
                            goto nd;
                    cxx.back().push_back(stk.back());
                    nd:
                    stk.pop_back();
                }
                cxx.back().push_back(k);
                stk.pop_back();
                cxx.push_back({});
            }
        }
        else // just using 1 back edge
            low[k] = min(low[k],h[to]);
    }
    if(t == 0 && nrfi == 1){
        nc[k] = 0;
    }
}
int main(){
    int n,m;
    cin >> n >> m;
    while(m--){
        int u,v;
        cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(vis[i]==0)
            dfs(i,0);
    cout << cxx.size()-1 << "\n";
    for(auto& cx : cxx){
        for(int el : cx)
            cout << el << " ";
        cout << "\n";
    }
}