Cod sursa(job #3374581)

Utilizator Costin707Geamanu Constantin Costin707 Data 9 noiembrie 2026 02:46:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

struct Muchie {
    int u, v;
};

vector<int> adj[MAXN];
int discovery_time[MAXN], low[MAXN];
bool visited[MAXN];
int timer = 0;

stack<Muchie> st;
vector<vector<int>> biconex_components;

void add_biconex_component(int u, int v) {
    vector<int> nodes;

    while (!st.empty()) {
        Muchie m = st.top();
        st.pop();

        nodes.push_back(m.u);
        nodes.push_back(m.v);

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

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

    biconex_components.push_back(nodes);
}

void dfs(int u, int parent = -1) {
    visited[u] = true;
    discovery_time[u] = low[u] = ++timer;

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

        if (visited[v]) {

            low[u] = min(low[u], discovery_time[v]);
            if (discovery_time[v] < discovery_time[u]) {
                st.push({u, v});
            }
        } else {

            st.push({u, v});
            dfs(v, u);

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


            if (low[v] >= discovery_time[u]) {
                add_biconex_component(u, v);
            }
        }
    }
}

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

    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 (!visited[i]) {
            dfs(i);
        }
    }


    fout << biconex_components.size() << "\n";


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

    return 0;
}