Cod sursa(job #3332373)

Utilizator DunareTanasescu Luca-Ioan Dunare Data 6 ianuarie 2026 13:28:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;
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()
{
    int x,y;
    f>>N>>M;P=1;
    for(int i=1;i<=M;++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFSpa(int x, int tata)
{
    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
        {
            DFSpa(y,x);
            Nma[x]=min(Nma[x],Nma[y]);
            if(x==1)
                nrFii++;
            else
            {
                if(Niv[x]<=Nma[y])
                    PA.insert(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);
            }
        }
    }
}

void DFSmc(int x, int tata)
{
    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
        {
            DFSmc(y,x);
            Nma[x]=min(Nma[x],Nma[y]);
            if(Niv[x]<Nma[y])
                MC.push_back(muchie(x,y));
        }
    }
}
int main()
{
    citire();
    switch(P)
    {
    case 1:
        DFScb(1,0);
        g<<nrCB<<'\n';
        for(int i=1; i<= nrCB; ++i)
        {
            //g<<CB[i].size()<<' ';
            for(const auto &x: CB[i])
                g<<x<<' ';
            g<<'\n';
        }
        break;
    case 2:
        DFSpa(1,0);
        if(nrFii>=2) PA.insert(1);
        g<<PA.size()<< '\n';
        for(const auto &x:PA)
            g<<x<<' ';
        break;
    case 3:
        DFSmc(1,0);
        g<<MC.size()<<'\n';
        for(const auto &m:MC)
            g<<m.x<<' '<<m.y<<'\n';
    }
    return 0;
}