Cod sursa(job #3220183)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 2 aprilie 2024 18:49:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
int n,m,p,i,x,y,k,nr,niv[100003],niv_min[100003],st[100003];
bool viz[100003];
vector <int> L[100003];
vector <int> comp_biconex[100003];
void dfs(int nod,int t)
{
    viz[nod]=1;
    niv[nod]=niv[t]+1;
    niv_min[nod]=min(niv_min[nod],niv[nod]);
    st[++nr]=nod;
    for(auto j:L[nod])
    {
        if(j!=t)
        {
            int fiu=j;
            if(!viz[fiu])
            {
                dfs(fiu,nod);
                niv_min[nod]=min(niv_min[nod],niv_min[fiu]);
                if(niv[nod]<=niv_min[fiu])///det componentelor biconexe
                {
                    while(st[nr]!=fiu)///det componentelor biconexe
                    {
                        comp_biconex[k].push_back(st[nr]);
                        nr--;
                    }
                    comp_biconex[k].push_back(fiu);
                    nr--;
                    comp_biconex[k].push_back(nod);
                    k++;
                }
            }
            else
                niv_min[nod]=min(niv_min[nod],niv[fiu]);
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        niv_min[i]=2e9;
    nr=0;
    k=1;
    niv[0]=0;
    niv[1]=1;
    niv_min[1]=1;
    dfs(1,0);
    fout<<k-1<<"\n";
    for(int i=1;i<k;i++)
    {
        for(auto j:comp_biconex[i])
            fout<<j<<" ";
        fout<<"\n";
    }

    return 0;
}