Cod sursa(job #2976584)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 9 februarie 2023 17:23:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

int const nmax = 1e5;

int n , m , viz[nmax + 5] , low[nmax + 5] , level[nmax + 5];
vector <int> adj[nmax + 5];
stack <pair<int,int>> st;

vector < vector <int> > ans;

static void impinge(int x,int y){
vector <int> sol;
int rx , ry;
do{
    rx = st.top().first;
    ry = st.top().second;
    sol.push_back(rx);
    sol.push_back(ry);
    st.pop();
}while(rx != x || ry != y);
ans.push_back(sol);
}

void dfs(int nod , int tata){
viz[nod] = 1;
level[nod] = level[tata] + 1;
low[nod] = level[nod];
for(auto x:adj[nod]){
    if(!viz[x]){
        st.push({nod,x});
        dfs(x , nod);
        low[nod] = min(low[nod] , low[x]);
        if(low[x] >= level[nod]){
            impinge(nod,x);
        }

    }else{
        low[nod] = min(low[nod] , level[x]);
    }
}
}

int main()
{
    freopen("biconex.in" , "r" , stdin);
    freopen("biconex.out" , "w" ,stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m;
    for(int i = 1;i <= m; ++i){
        int x , y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    cout << ans.size() << "\n";
    for(auto &x:ans){
        sort(x.begin(),x.end());
        x.erase(unique(x.begin(),x.end()),x.end());
        for(auto const y : x)cout << y  << " ";
        cout << "\n";
    }
}