Cod sursa(job #3361657)

Utilizator ililogIlinca ililog Data 27 iulie 2026 13:37:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
/*Determinare componente biconexe si puncte de articulatie*/
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

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

#define NMAX 100005

int n, m;
vector<int> G[NMAX];
int nivel[NMAX], lowest[NMAX]; 
vector < vector <int> > Sol;
stack<int> stiva;

void dfs(int nod, int level = 1) {
    nivel[nod] = level;
    lowest[nod] = level; //presupun ca nu se poate intoarce
    stiva.push(nod);

    for (auto vecin: G[nod]) {
        if (vecin == nod) continue;
        if (nivel[vecin] > 0) { //muchie de intoarcere
            lowest[nod] = min(lowest[nod], nivel[vecin]);
        } else {
            dfs(vecin, level+1);
            lowest[nod] = min(lowest[nod], lowest[vecin]);
            if (lowest[vecin] >= nivel[nod]) { //vecin nu poate sari mai mult de nod -> nod articulatie
                vector<int> comp;
                int popped;
                do {
                    popped = stiva.top();
                    comp.push_back(popped);
                    stiva.pop();
                } while (popped != vecin);
                comp.push_back(nod);
                Sol.push_back(comp);
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        int u,v; fin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i = 1; i<=n; i++) {
        if (!nivel[i]) {
            dfs(i);
        }
    }

    fout << Sol.size() << '\n';
    for (auto &c: Sol) {
        for (auto nod: c) {
            fout << nod << ' ';
        }
        fout << '\n';
    }
    
    return 0;
}