Cod sursa(job #3336976)

Utilizator anon123andrei popescu anon123 Data 26 ianuarie 2026 20:05:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

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

vector<vector<int>> lista;
vector<bool> viz;
vector<int> tata;
stack<pair<int,int>> stk;
vector<int> nivel;
vector<int> niv_min;
// int cbc;
int n,m;
vector<set<int>> conexe;
void biconexa(int u, int v) {
    set<int> tmp;
    int x,y;
    do {
        x = stk.top().first;
        y= stk.top().second;
        stk.pop();
        tmp.insert(x);
        tmp.insert(y);
    }while (x!=u || y!=v);
    conexe.push_back(tmp);
}
void dfs(int i) {
    niv_min[i] = nivel[i];
    for (int v : lista[i]) {
        if (v != tata[i]) {

            if (!viz[v]) {
                nivel[v] = nivel[i] + 1;
                tata[v] = i;
                viz[v] = true;
                stk.emplace(i,v);
                dfs(v);
                niv_min[i] = min(niv_min[i], niv_min[v]);
                if (nivel[i] <= niv_min[v]) {
                    // ceva
                    // cout<<"punct/muchie critica, "<<i<<" "<<v<<endl;
                    // scoatem de pe stiva tot pana la i,v
                    biconexa(i,v);
                }
            }
            else {
                // muchie intoarcere
                niv_min[i] = min(nivel[v], niv_min[i]);
            }
        }
    }
}
int main(){
    fin >> n>>m;
    lista.resize(n+1);
    viz.resize(n+1, false);
    tata.resize(n+1);
    nivel.resize(n+1);
    niv_min.resize(n+1);
    for (int i = 0; i<m; i++) {
        int u,v;
        fin>>u>>v;
        lista[u].push_back(v);
        lista[v].push_back(u);
    }
    for (int i = 1; i<=n ; i++) {
        if (!viz[i]) {
            viz[i] = true;
            tata[i] = 0;
            nivel[i] = 1;
            dfs(i);
        }
    }
    fout<<conexe.size()<<endl;
    for (auto cmp : conexe) {
        for (auto nod : cmp) {
            fout<< nod<<" ";
        }
        fout<<endl;
    }



    return 0;
}