Cod sursa(job #3376646)

Utilizator carabusuAndrei Victor carabusu Data 18 noiembrie 2026 19:32:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.16 kb
#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    fin >> N >> M;

    vector<vector<pair<int, int>>> graf(N + 1);
    vector<int> capat1(M), capat2(M);
    for (int i = 0; i < M; ++i) {
        fin >> capat1[i] >> capat2[i];
        graf[capat1[i]].push_back({capat2[i], i});
        graf[capat2[i]].push_back({capat1[i], i});
    }

    vector<int> descoperire(N + 1, 0), minim(N + 1, 0);
    vector<int> parinte(N + 1, 0), muchie_parinte(N + 1, -1);
    vector<int> urmator_vecin(N + 1, 0), stiva_muchii;
    vector<int> marcaj(N + 1, 0);
    vector<vector<int>> componente;
    int timp = 0;

    for (int start = 1; start <= N; ++start) {
        if (descoperire[start] != 0) {
            continue;
        }

        if (graf[start].empty()) {
            componente.push_back({start});
            descoperire[start] = minim[start] = ++timp;
            continue;
        }

        vector<int> stiva_noduri = {start};
        descoperire[start] = minim[start] = ++timp;

        while (!stiva_noduri.empty()) {
            int nod = stiva_noduri.back();

            if (urmator_vecin[nod] < static_cast<int>(graf[nod].size())) {
                auto [vecin, indice_muchie] = graf[nod][urmator_vecin[nod]++];

                if (indice_muchie == muchie_parinte[nod]) {
                    continue;
                }

                if (descoperire[vecin] == 0) {
                    parinte[vecin] = nod;
                    muchie_parinte[vecin] = indice_muchie;
                    stiva_muchii.push_back(indice_muchie);
                    descoperire[vecin] = minim[vecin] = ++timp;
                    stiva_noduri.push_back(vecin);
                } else if (descoperire[vecin] < descoperire[nod]) {
                    stiva_muchii.push_back(indice_muchie);
                    minim[nod] = min(minim[nod], descoperire[vecin]);
                }
            } else {
                stiva_noduri.pop_back();
                int tata = parinte[nod];

                if (tata != 0) {
                    minim[tata] = min(minim[tata], minim[nod]);
                    if (minim[nod] >= descoperire[tata]) {
                        vector<int> componenta;
                        int id = componente.size() + 1;
                        int muchie;
                        do {
                            muchie = stiva_muchii.back();
                            stiva_muchii.pop_back();
                            for (int capat : {capat1[muchie], capat2[muchie]}) {
                                if (marcaj[capat] != id) {
                                    marcaj[capat] = id;
                                    componenta.push_back(capat);
                                }
                            }
                        } while (muchie != muchie_parinte[nod]);
                        componente.push_back(componenta);
                    }
                }
            }
        }
    }

    fout << componente.size() << '\n';
    for (const vector<int>& componenta : componente) {
        for (int nod : componenta) {
            fout << nod << ' ';
        }
        fout << '\n';
    }

    return 0;
}