Cod sursa(job #3373809)

Utilizator vik4torTunaru Victor-Cristian vik4tor Data 7 noiembrie 2026 22:26:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bitset>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <utility>

using namespace std;

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

vector<vector<int>> graf;
vector<int> dist;
vector<int> low;
vector<pair<int, int>> comp;
vector<unordered_set<int>> componente;
int timp;

constexpr int NMAX = 100005;
bitset<NMAX> vizitat;

void construieste_componenta(int u, int v) {
    unordered_set<int> noduri;
    pair<int, int> muchie;
    do {
        muchie = comp.back();
        comp.pop_back();
        noduri.insert(muchie.first);
        noduri.insert(muchie.second);
    } while (muchie.first != u || muchie.second != v); // Ne oprim la muchia (u, v)

    componente.push_back(noduri);
}

void dfs(int u, int p = -1) {
    vizitat.set(u);
    dist[u] = low[u] = ++timp;
    for (int v : graf[u]) {
        if (v == p) continue;
        if (vizitat[v]) {
            low[u] = min(low[u], dist[v]);
            if (dist[v] < dist[u]) {
                comp.emplace_back(u, v);
            }
        }
        else {
            comp.emplace_back(u, v);
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dist[u]) {
                construieste_componenta(u, v);
            }
        }
    }
}

int main() {
    timp = 0;
    int N, M;
    fin >> N >> M;
    graf.resize(N + 1);
    dist.assign(N + 1, -1);
    low.assign(N + 1, -1);
    for (int i = 0; i < M; i++) {
        int u, v;
        fin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    for (int i = 1; i <= N; i++) {
        if (!vizitat[i]) dfs(i);
    }
    fout << componente.size() << '\n';
    for (auto& componenta : componente) {
        for (int nod : componenta) {
            fout << nod << ' ';
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
}