Cod sursa(job #3374877)

Utilizator LucaG.LucaG. LucaG. Data 9 noiembrie 2026 17:01:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>

using namespace std;

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

const int MAXN = 100005;

struct Edge {
    int u, v;
};

vector<int> adj[MAXN];
int tin[MAXN], low[MAXN];
int timer = 0;
stack<Edge> st;

vector<vector<int>> bcc_list;

void dfs(int u, int p = 0) {
    tin[u] = low[u] = ++timer;

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

        if (tin[v]) {
            // Muchie de intoarcere
            low[u] = min(low[u], tin[v]);
            if (tin[v] < tin[u]) {
                st.push({u, v});
            }
        } else {
            // Muchie de arbore
            st.push({u, v});
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= tin[u]) {
                vector<int> current_bcc;
                unordered_set<int> unique_nodes;

                while (true) {
                    Edge e = st.top();
                    st.pop();

                    unique_nodes.insert(e.u);
                    unique_nodes.insert(e.v);

                    if (e.u == u && e.v == v) break;
                }

                current_bcc.assign(unique_nodes.begin(), unique_nodes.end());
                bcc_list.push_back(current_bcc);
            }
        }
    }
}

int main() {
    int n, m;
    if (!(fin >> n >> m)) return 0;

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

    for (int i = 1; i <= n; ++i) {
        if (!tin[i]) {
            dfs(i, 0);
        }
    }

    fout << bcc_list.size() << "\n";
    for (const auto& bcc : bcc_list) {
        for (size_t i = 0; i < bcc.size(); ++i) {
            fout << bcc[i] << (i + 1 == bcc.size() ? "" : " ");
        }
        fout << "\n";
    }

    return 0;
}