Cod sursa(job #2651625)

Utilizator adiaioanaAdia R. adiaioana Data 23 septembrie 2020 09:46:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector <vector <int> > C;
vector <int> st, G[100100];
int nvl[100100], N;
int dfs(int nod,int ant,int lvl)
{
    int mn=lvl;
    nvl[nod]=lvl;
    st.push_back(nod);
    for(auto nn:G[nod])
    {
        if(nn==ant)
            continue;
        if(nvl[nn])
        {
            mn=min(mn,nvl[nn]);
            continue;
        }
        mn=min(mn,dfs(nn,nod,lvl+1));
    }

    if(ant && mn>=lvl-1)
    {
        vector <int> nul;
        nul.clear();
        while(!st.empty() && st.back()!=nod)
        {
            nul.push_back(st.back());
            st.pop_back();
        }
        nul.push_back(nod);
        nul.push_back(ant);
        //reverse (nul.begin(),nul.end());
        st.pop_back();
        C.push_back(nul);
    }
    return mn;
}

int main()
{
    int M,x,y;
    cin>>N>>M;
    for(int i=1; i<=M; ++i)
    {
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    M=dfs(1,0,1);
    cout<<C.size()<<'\n';
    for(auto it: C){
        for(auto it1:it)
            cout<<it1<<' ';
        cout<<'\n';
    }
    return 0;
}