Cod sursa(job #3374572)

Utilizator RDS1208Rosu David Stefan RDS1208 Data 9 noiembrie 2026 02:34:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

vector<vector<int>> graf;
vector<int> timpDescoperire, timpMinim;
vector<vector<int>> componente;
stack<pair<int, int>> stiva;

int timer = 0;

void extrage(int nod, int vecin) {
    vector<int> componenta;

    while (true) {
        auto [x, y] = stiva.top();
        stiva.pop();

        componenta.push_back(x);
        componenta.push_back(y);

        if (x == nod && y == vecin)
            break;
    }

    sort(componenta.begin(), componenta.end());
    componenta.erase(
        unique(componenta.begin(), componenta.end()),
        componenta.end()
    );

    componente.push_back(componenta);
}

void dfs(int nod, int parinte) {
    timpDescoperire[nod] = timpMinim[nod] = ++timer;

    for (int vecin : graf[nod]) {
        if (vecin == parinte)
            continue;

        if (timpDescoperire[vecin] == 0) {
            stiva.push({nod, vecin});

            dfs(vecin, nod);

            timpMinim[nod] = min(timpMinim[nod], timpMinim[vecin]);

            if (timpMinim[vecin] >= timpDescoperire[nod])
                extrage(nod, vecin);
        }
        else if (timpDescoperire[vecin] < timpDescoperire[nod]) {
            stiva.push({nod, vecin});
            timpMinim[nod] = min(timpMinim[nod], timpDescoperire[vecin]);
        }
    }
}

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

    int n, m;
    fin >> n >> m;

    graf.resize(n + 1);
    timpDescoperire.resize(n + 1, 0);
    timpMinim.resize(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;

        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (timpDescoperire[i] == 0)
            dfs(i, 0);
    }

    fout << componente.size() << '\n';

    for (const auto& componenta : componente) {
        for (int nod : componenta)
            fout << nod << ' ';

        fout << '\n';
    }

    return 0;
}