Cod sursa(job #3294199)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 18 aprilie 2025 22:42:13
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 2000000000
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");


vector<int> graf[VMAX];
int adancime[VMAX];
bool vizitat[VMAX];
bool biconex[VMAX];
vector<int> stiva,grupe_biconexe[VMAX];
int nr_grupe;

int dfs_afla_biconexe(int nod, int parinte)
{
    vizitat[nod]=1;
    adancime[nod]=adancime[parinte]+1;
    stiva.push_back(nod);
    int minim = INF;
    int nr;
    for(auto i:graf[nod])
    {
        if(vizitat[i]==0)
        {
            nr=dfs_afla_biconexe(i,nod);
            minim=min(nr,minim);
            if(nr>=adancime[nod]) // componenta biconexa
            {
                while(stiva.back()!=nod)
                {
                    grupe_biconexe[nr_grupe].push_back(stiva.back());
                    stiva.pop_back();
                }
                grupe_biconexe[nr_grupe].push_back(nod);
                nr_grupe++;
            }
        }
        else if(i!=parinte)// muchie de intoarcere
        {
            minim = min(minim,adancime[i]);
        }
    }
    return minim;
}
int dfs_grupe(int nod) // daca apelam dintr-un nod biconex nu mai avem cazul in care nu luam nodul initial intr-o grupa
{
    vizitat[nod]=1;
    stiva.push_back(nod);
    for(auto i:graf[nod])
    {
        if(vizitat[nod]==0)
        {
            dfs_grupe(i);
            if(biconex[nod]) // avem o grupa de biconexe
            {
                while(stiva.back()!=nod)
                {
                    grupe_biconexe[nr_grupe].push_back(stiva.back());
                    stiva.pop_back();
                }
                grupe_biconexe[nr_grupe].push_back(nod);
                nr_grupe++;
            }
        }
    }
}

int main()
{
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k;
        graf[j].push_back(k);
        graf[k].push_back(j);
    }
    dfs_afla_biconexe(1,0);

    if(stiva.size()>1) // mai e o componenta neadaugata
    {
        while(stiva.size())
        {
            grupe_biconexe[nr_grupe].push_back(stiva.back());
            stiva.pop_back();
        }
        nr_grupe++;
    }
    fout<<nr_grupe<<'\n';
    for(i=0;i<nr_grupe;i++)
    {
        for(j=0;j<grupe_biconexe[i].size();j++)
            fout<<grupe_biconexe[i][j]<<' ';
        fout<<'\n';
    }

    return 0;
}