Cod sursa(job #3374608)

Utilizator Lleonardo211Leonardo-Ioan Leonte Lleonardo211 Data 9 noiembrie 2026 03:54:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, m;

vector<vector<int>> prieteni;
vector<int> depth;                     //momentul descoperirii in DFS
vector<int> lowest;                    //cel mai mic depth atins de subarbore printr-o scurtatura
vector<int> stiva;                     //nodurile descoperite, care inca nu sunt intr-o componenta
vector<vector<int>> componente;        //componentele biconexe gasite
int contor = 0;

void dfs(int nod, int parinte) {
    depth[nod] = lowest[nod] = ++contor;
    stiva.push_back(nod);

    for (int vecin : prieteni[nod]) {
        if (depth[vecin] == 0) {
            //vecin nevizitat, fiu in arborele DFS
            dfs(vecin, nod);
            lowest[nod] = min(lowest[nod], lowest[vecin]);

            //subarborele lui vecin nu urca deasupra  lui => subarborele + nod formeaza o componenta biconexa
            if (lowest[vecin] >= depth[nod]) {
                vector<int> componenta;
                int x;
                do {
                    x = stiva.back();
                    stiva.pop_back();
                    componenta.push_back(x);
                } while (x != vecin);         //golim stiva pana la vecin, inclusiv

                componenta.push_back(nod);
                componente.push_back(componenta);
            }
        }
        else if (vecin != parinte) {
            //vecin deja vizitat, nu e parintele => scurtatura
            lowest[nod] = min(lowest[nod], depth[vecin]);
        }
    }
}

int main() {
    fin >> n >> m;

    prieteni.resize(n + 1);
    depth.assign(n + 1, 0);
    lowest.assign(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        prieteni[x].push_back(y);
        prieteni[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (depth[i] == 0) {
            dfs(i, 0);
            stiva.pop_back();         //scoatem radacina
        }
    }

    fout << componente.size() << '\n';
    for (const auto& componenta : componente) {
        for (int x : componenta)
            fout << x << ' ';
        fout << '\n';
    }

    return 0;
}