Cod sursa(job #3322840)

Utilizator andreea0146Nicula Andreea andreea0146 Data 15 noiembrie 2025 21:50:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
const int NMAX=100001;

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

struct muchie
{
    int x,y;
    muchie(int xx=0,int yy=0)
    {
        x=xx,y=yy;
    }
};

int p,n,m,nrfii,nrcb,
    niv[NMAX],nma[NMAX],
    s[NMAX],vf;

vector<int>g[NMAX],cb[NMAX];
vector<muchie>mc;
set<int>pa;
bool viz[NMAX];

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfscb(int x,int tata)
{
    s[++vf]=x;
    viz[x]=1;
    niv[x]=niv[tata]+1;
    nma[x]=niv[x];
    for(const auto &y:g[x])
    {
        if(y==tata) continue;
        if(viz[y])
            nma[x]=min(nma[x],niv[y]);
        else
        {
            dfscb(y,x);
            nma[x]=min(nma[x],nma[y]);
            if(niv[x]<=nma[y])
            {
                nrcb++;
                while(s[vf]!=y)
                    cb[nrcb].push_back(s[vf--]);
                cb[nrcb].push_back(y);
                --vf;
                cb[nrcb].push_back(x);
            }
        }
    }
}

int main()
{
    citire();
    dfscb(1,0);
    fout<<nrcb<<'\n';
    for(int i=1; i<=nrcb; i++)
    {
        for(const auto &x:cb[i])
            fout<<x<<' ';
        fout<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}