Cod sursa(job #3148218)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 29 august 2023 21:58:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#define max_sz 100003

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

int n,m;

vector <int> v[max_sz];

vector <int> st;

bool viz[max_sz];
int lv[max_sz];
int mlv[max_sz];

int comp_nr;

vector <int> sol[max_sz];


void dfs(int nod,int p)
{
    viz[nod]=true;
    lv[nod]=lv[p]+1;
    mlv[nod]=lv[nod];
    st.push_back(nod);

    for(auto& i : v[nod])
        if(i!=p)
        {
            if(viz[i])
                mlv[nod]=min(mlv[nod],lv[i]);

            else
            {
                dfs(i,nod);
                mlv[nod]=min(mlv[nod],mlv[i]);

                if(mlv[i]>=lv[nod])
                {
                    comp_nr++;
                    while(st.back()!=i)
                    {
                        sol[comp_nr].push_back(st.back());
                        st.pop_back();
                    }
                    sol[comp_nr].push_back(i);
                    st.pop_back();
                    sol[comp_nr].push_back(nod);
                }

            }
        }
}



int main()
{
    fin>>n>>m;
    for(int i =1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
            dfs(i,0);
    }
    fout<<comp_nr<<'\n';
    for(int i=1; i<=comp_nr; i++)
    {
        for(auto& j : sol[i])
            fout<<j<<' ';
        fout<<'\n';
    }

}