Cod sursa(job #3372687)

Utilizator ilystefalexVaduva Stefan-Alexandru ilystefalex Data 4 noiembrie 2026 18:32:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
//
// Created by Alex on 11/3/2026.
//
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
int N,M;
vector<vector<int>> graf;
stack<int> st;
vector<vector<int>> rez;
vector<int>lowlink;
vector<int>nivel;

int niv_crt=1;
void dfs(int n,int parinte) {
    nivel[n]=niv_crt;
    lowlink[n]=niv_crt;
    niv_crt++;
    st.push(n);

    for (int nod : graf[n]) {
        if (nod==parinte) continue;
        if (nivel[nod]==0) {
            dfs(nod,n);
            lowlink[n]=min(lowlink[n],lowlink[nod]);
    if (lowlink[nod]>=nivel[n]) {
        vector<int> tmp;

            while (!st.empty() && st.top() != nod ) {
                tmp.push_back(st.top());
                st.pop();

            }
            if (!st.empty()) {
               tmp.push_back(st.top());
            st.pop();
            }
        tmp.push_back(n);

            rez.push_back(tmp);

    }
        }else{
            lowlink[n]=min(lowlink[n],nivel[nod]);

        }
    }



}
void rezolvare() {
    dfs(1,0);


}

void citire() {
    ifstream fin("biconex.in");
    fin>>N>>M;
    graf.resize(N + 1);
    nivel.resize(N + 1,0);
    lowlink.resize(N + 1);
    for (int i=0;i<M ;i++) {
        int x,y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);

    }
    fin.close();
}
void afisare() {
    ofstream fout("biconex.out");
    fout<<rez.size()<<endl;
    for (int i=0;i<rez.size();i++) {
        for (int j=0;j<rez[i].size();j++) {
            fout<<rez[i][j]<<" ";
        }
        fout<<endl;
    }
}



int main() {
    citire();
    rezolvare();
    afisare();









}