Cod sursa(job #2801989)

Utilizator Andrei012Trache Andrei Andrei012 Data 17 noiembrie 2021 12:15:59
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
#define mp make_pair

ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> v[100001];
stack<pair<int,int> > st;
vector<pair<int,int> > cbi[100001];

int depth[100001],parc[100001],ans;

int dfs(int node){
    parc[node]=1;
    int up=(1<<30);
    for(auto i : v[node]){
        st.push(make_pair(node,i));

        if(parc[i]==1){
            if(depth[node]<=depth[i])
                st.pop();
            up=min(up,depth[i]);
            continue;
        }
        else{
            depth[i]=depth[node]+1;
            int nodeant=dfs(i);
            up=min(up,nodeant);
            if(nodeant>=depth[node]){
                ++ans;
                while(st.size() && st.top() != mp(node,i)){
                    cbi[ans].push_back(st.top());
                    st.pop();
                }
                cbi[ans].push_back(st.top());
                st.pop();
            }
        }
    }
    return up;

}


int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    out<<ans<<'\n';
    for(i=1;i<=ans;++i){
        for(auto j : cbi[i])
            out<<j.first<<" "<<j.second<<'\n';
        out<<'\n';
    }
    return 0;
}