Cod sursa(job #3372800)

Utilizator lucainfoOlteanu Luca lucainfo Data 5 noiembrie 2026 00:43:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

vector<vector<int>> adj;
vector<int> disc, low, parent;
vector<bool> viz;
stack<pair<int, int>> stivaMuchii; // stiva pentru muchii
vector<vector<int>> componente;    // rezultatul final
int timp = 0;

void dfs(int u) {
    viz[u] = true;
    disc[u] = low[u] = ++timp;

    for (int v : adj[u]) {
        if (!viz[v]) {
            parent[v] = u;
            stivaMuchii.push({u, v}); //adaugam pe stiva prima muchie
            dfs(v);
            low[u] = min(low[u], low[v]);//actualizam low la intoarcere

            if (low[v] >= disc[u]) {//verificam daca am gasit componenta
                vector<int> comp;
                while (true) {
                    pair<int, int> muchie = stivaMuchii.top();
                    stivaMuchii.pop();
                    comp.push_back(muchie.first);
                    comp.push_back(muchie.second);
                    if (muchie.first == u && muchie.second == v) break;
                }
                sort(comp.begin(), comp.end());//sortam
                comp.erase(unique(comp.begin(), comp.end()), comp.end());//eliminam duplicate
                componente.push_back(comp);
            }
        } else if (v != parent[u] && disc[v] < disc[u]) {// daca e vizitat, nu e parinte si a fost descoperit inainte =>
            stivaMuchii.push({u, v});//muchie de intoarcere, o adaugam
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    int N, M;
    fin >> N >> M;

    adj.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    disc.assign(N + 5, -1);
    low.assign(N + 5, 0);
    parent.assign(N + 5, -1);
    viz.assign(N + 5, false);

    for (int i = 1; i <= N; ++i) {
        if (!viz[i]) {
            dfs(i);
        }
    }

    fout << componente.size() << "\n";
    for (auto& comp : componente) {
        for (int nod : comp) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}