Cod sursa(job #3291216)

Utilizator mihai_bosIancu Mihai mihai_bos Data 3 aprilie 2025 18:41:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.45 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int NMAX = 1e5 + 5;
int t, n, m, i, nma[NMAX], niv[NMAX], viz[NMAX], copii_radacina;
vector<int> v[NMAX], puncteart;
vector<pair<int, int>> punti; // pentru stocarea punților (bridges)

// pentru componente biconexe
vector<vector<pair<int, int>>> componente_biconexe;
stack<pair<int, int>> stiva;

bool estePunctArt[NMAX];

// Funcţie helper pentru extragerea unei componente biconexe din stivă
void extractComponent(pair<int, int> targetEdge) {
    vector<pair<int, int>> componenta;
    // Scoate din stivă până când se întâlneşte marginea targetEdge
    while (!stiva.empty()) {
        auto edge = stiva.top();
        stiva.pop();
        componenta.push_back(edge);
        if (edge == targetEdge)
            break;
    }
    componente_biconexe.push_back(componenta);
}

void dfs(int nod, int tata) {
    viz[nod] = 1;
    niv[nod] = niv[tata] + 1;
    nma[nod] = niv[nod];

    for (auto vec : v[nod]) {
        if (vec == tata)
            continue;

        if (viz[vec]) {
            if (niv[vec] < nma[nod]) {
                nma[nod] = niv[vec];
                stiva.push({nod, vec});
            }
        } else {
            if (tata == 0)
                copii_radacina++;
            stiva.push({nod, vec});
            dfs(vec, nod);

            nma[nod] = min(nma[nod], nma[vec]);

            if (niv[nod] <= nma[vec]) {
                if (nod != 1 && !estePunctArt[nod]) {
                    estePunctArt[nod] = true;
                    puncteart.push_back(nod);
                }
                if (niv[nod] < nma[vec])
                    punti.push_back({nod, vec});

                extractComponent({nod, vec});
            }
        }
    }
}

int main() {
    in  >> n >> m;
    while (m--) {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    // Tratarea cazului special pentru rădăcină
    if (copii_radacina >= 2) {
        estePunctArt[1] = true;
        puncteart.push_back(1);
    }

    // Afisarea rezultatului în funcţie de tipul de cerinţă
    //if (t == 1) {
        out << componente_biconexe.size() << '\n';
        for (auto comp : componente_biconexe) {
            vector<int> noduri;
            for (auto edge : comp) {
                noduri.push_back(edge.first);
                noduri.push_back(edge.second);
            }
            sort(noduri.begin(), noduri.end());

            // Elimină duplicatele
            vector<int> noduri_unice;
            if (!noduri.empty()) {
                noduri_unice.push_back(noduri[0]);
                for (int i = 1; i < noduri.size(); ++i) {
                    if (noduri[i] != noduri[i - 1])
                        noduri_unice.push_back(noduri[i]);
                }
            }

           // out << noduri_unice.size() << ' ';
            for (int x : noduri_unice)
                out << x << ' ';
            out << '\n';
        }

    //else if (t == 2) {
     //   out << puncteart.size() << '\n';
     //   for (auto x : puncteart)
     //       out << x << ' ';
    //}
   // else {
    //    out << punti.size() << '\n';
    //    for (auto x : punti)
    //        out << x.first << ' ' << x.second << '\n';
   // }

    return 0;
}