Cod sursa(job #3372084)

Utilizator david18.6yDavid Popa david18.6y Data 2 noiembrie 2026 14:39:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

vector<vector<int>> lista, comp;
vector<int> ordine, ocolire, parinte;
stack<pair<int,int>> stiva_muchii;
int moment = 0;

void dfs(int nod) {
    if (ordine[nod] != 0) return;

    moment++;
    ordine[nod] = moment;
    ocolire[nod] = ordine[nod];
    int copii_descoperiti = 0;

    for (int vecin : lista[nod]) {
        if (vecin == parinte[nod]) {
            continue;
        } else if (ordine[vecin] != 0) {
            ocolire[nod] = min(ocolire[nod], ordine[vecin]);
            if (ordine[vecin] < ordine[nod])
                stiva_muchii.push({nod, vecin});
        } else {
            parinte[vecin] = nod;
            copii_descoperiti++;
            stiva_muchii.push({nod, vecin});
            dfs(vecin);
            ocolire[nod] = min(ocolire[nod], ocolire[vecin]);
            if (ocolire[vecin] >= ordine[nod]) {
                vector<int> componenta;
                while (true) {
                    pair<int,int> m = stiva_muchii.top();
                    stiva_muchii.pop();
                    componenta.push_back(m.first);
                    componenta.push_back(m.second);
                    if (m == make_pair(nod, vecin)) break;
                }
                sort(componenta.begin(), componenta.end());
                componenta.erase(unique(componenta.begin(), componenta.end()),
                                 componenta.end());
                comp.push_back(componenta);
            }
        }
    }
}

int main() {
    ifstream f("biconex.in");
    ofstream g("biconex.out");

    int N, M;
    f >> N >> M;
    lista.resize(N + 1);
    ordine.assign(N + 1, 0);
    ocolire.assign(N + 1, 0);
    parinte.assign(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int x, y;
        f >> x >> y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }

    for (int nod = 1; nod <= N; nod++)
        dfs(nod);

    g << comp.size() << "\n";
    for (auto &c : comp) {
        for (int x : c) g << x << " ";
        g << "\n";
    }
    return 0;
}