Cod sursa(job #3328955)

Utilizator Mateixx1Trandafir Matei Mateixx1 Data 11 decembrie 2025 12:33:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <vector>
#include <fstream>
using namespace std;
const int NMAX=100100;
int x,y,n,m,comp,Niv[NMAX],Nma[NMAX],viz[NMAX],vf,S[NMAX];
vector<int>G[NMAX],CB[NMAX];
ifstream f("biconex.in");
ofstream g("biconex.out");

void DFS(int nod,int tata) {
    S[++vf]=nod;
    Niv[nod]=Niv[tata]+1;
    viz[nod]=1;
    Nma[nod]=Niv[nod];
    for(const int&i:G[nod]) {
        if(i==tata) {
            continue;
        }
        if(viz[i]==1) {
            Nma[nod]=min(Nma[nod],Niv[i]);
        } else {
            DFS(i,nod);
            Nma[nod]=min(Nma[nod],Nma[i]);
            if(Niv[nod]<=Nma[i]) {
                comp++;
                while(S[vf]!=i) {
                    CB[comp].push_back(S[vf--]);
                }
                CB[comp].push_back(i);
                vf--;
                CB[comp].push_back(nod);
            }
        }
    }
}


int main() {
    f>>n>>m;
    while(m--) {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1,0);
    g<<comp<<'\n';
    for(int i=1; i<=comp; ++i) {
        for(const int &j:CB[i]) {
            g<<j<<' ';
        }
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}