Cod sursa(job #2667892)

Utilizator @stefansevastre@Stefan Sevastre @stefansevastre@ Data 4 noiembrie 2020 00:38:23
Problema Componente biconexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <vector <int> > C;
vector <int> st, G[100000];
int nvl[100000], 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);
        st.pop_back();
        C.push_back(nul);
    }
    return mn;
}

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

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