Cod sursa(job #2425503)

Utilizator gabrielmGabriel Majeri gabrielm Data 24 mai 2019 21:07:04
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

vector<vector<int>> graf;
vector<int> stiva, adanc, minim;
vector<vector<int>> componente;
vector<bool> vizitat;

void DFS(int pred, int nod) {
    vizitat[nod] = true;
    minim[nod] = adanc[nod] = adanc[pred] + 1;
    stiva.push_back(nod);

    for (int vecin : graf[nod]) {
        // ignoram muchia pe care am venit
        if (vecin == pred) {
            continue;
        }

        // asta e muchie de intoarcere
        if (vizitat[vecin]) {
            minim[nod] = min(minim[nod], adanc[vecin]);
        }
        // muchie de inaintare
        else {
            DFS(nod, vecin);

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

            if (adanc[nod] > minim[vecin]) {
                continue;
            }

            vector<int> comp;

            // ne intoarcem pe stiva pentru a determina
            // intreaga componenta biconexa
            while (stiva.back() != vecin) {
                comp.push_back(stiva.back());
                stiva.pop_back();
            }
            stiva.pop_back();
            comp.push_back(vecin);

            comp.push_back(nod);

            componente.push_back(comp);
        }
    }
}

int main() {
    ifstream in("biconex.in");

    int n;
    in >> n;

    graf.resize(n + 1);
    vizitat.resize(n + 1);
    adanc.resize(n + 1);
    minim.resize(n + 1);

    int m;
    in >> m;

    for (int i = 0; i < m; ++i) {
        int start, end;
        in >> start >> end;

        graf[start].push_back(end);
        graf[end].push_back(start);
    }

    DFS(0, 1);

    ofstream out("biconex.out");

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

    for (const auto& comp : componente) {
        for (int nod : comp) {
            out << nod << ' ';
        }
        out << '\n';
    }
    out << '\n';
}