Cod sursa(job #3375172)

Utilizator rxzvyMatei Razvan rxzvy Data 10 noiembrie 2026 19:29:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

struct Edge {
    int u, v;
};

vector<int> adj[MAXN];
int disc[MAXN], low[MAXN];
int timer = 0;

vector<Edge> st;
vector<vector<int>> bcc;

void dfs(int u, int parent) {
    disc[u] = low[u] = ++timer;

    for (int v : adj[u]) {
        if (v == parent) continue;

        if (disc[v] != 0) {
            low[u] = min(low[u], disc[v]);
            if (disc[v] < disc[u]) {
                st.push_back({u, v});
            }
        } else {
            st.push_back({u, v});
            dfs(v, u);

            low[u] = min(low[u], low[v]);

            if (low[v] >= disc[u]) {
                vector<int> comp;
                while (true) {
                    Edge e = st.back();
                    st.pop_back();
                    comp.push_back(e.u);
                    comp.push_back(e.v);
                    if (e.u == u && e.v == v) break;
                }

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

                bcc.push_back(comp);
            }
        }
    }
}

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (disc[i] == 0) {
            if (adj[i].empty()) {
                bcc.push_back({i});
            } else {
                dfs(i, 0);
            }
        }
    }

    cout << bcc.size() << "\n";
    for (int i = 0; i < bcc.size(); ++i) {
        for (int j = 0; j < bcc[i].size(); ++j) {
            cout << bcc[i][j] << (j + 1 == bcc[i].size() ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}