Cod sursa(job #3374713)

Utilizator Memetel_LaviniaMemetel Mariana Lavinia Memetel_Lavinia Data 9 noiembrie 2026 09:35:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MAX_NODURI = 100005;

struct Muchie {
    int sursa, destinatie;
};

vector<int> lista_adiacenta[MAX_NODURI];
int nivel[MAX_NODURI], nivel_minim[MAX_NODURI];
int timp;

vector<Muchie> stiva_muchii;
vector<vector<int>> toate_componentele;

void dfs(int nod, int parinte) {
    timp++;
    nivel[nod] = nivel_minim[nod] = timp;

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

        if (nivel[vecin] != 0) {
            nivel_minim[nod] = min(nivel_minim[nod], nivel[vecin]);
            if (nivel[vecin] < nivel[nod]) {
                stiva_muchii.push_back({nod, vecin});
            }
        } else {
            stiva_muchii.push_back({nod, vecin});
            dfs(vecin, nod);
            nivel_minim[nod] = min(nivel_minim[nod], nivel_minim[vecin]);

            if (nivel_minim[vecin] >= nivel[nod]) {
                vector<int> componenta_curenta;

                while (true) {
                    Muchie muchie_curenta = stiva_muchii.back();
                    stiva_muchii.pop_back();

                    componenta_curenta.push_back(muchie_curenta.sursa);
                    componenta_curenta.push_back(muchie_curenta.destinatie);

                    if (muchie_curenta.sursa == nod && muchie_curenta.destinatie == vecin) {
                        break;
                    }
                }

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

                toate_componentele.push_back(componenta_curenta);
            }
        }
    }
}

int main() {
    int numar_noduri, numar_muchii;
    fin >> numar_noduri >> numar_muchii;

    for (int i = 0; i < numar_muchii; i++) {
        int nod1, nod2;
        fin >> nod1 >> nod2;
        lista_adiacenta[nod1].push_back(nod2);
        lista_adiacenta[nod2].push_back(nod1);
    }

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

    fout << toate_componentele.size() << "\n";
    for (const auto& componenta : toate_componentele) {
        for (int i = 0; i < (int)componenta.size(); i++) {
            fout << componenta[i] << (i + 1 == (int)componenta.size() ? "" : " ");
        }
        fout << "\n";
    }

    return 0;
}