Cod sursa(job #3309463)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 4 septembrie 2025 20:44:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 100000;
const int INF = MAX_N + 1;

vector<vector<int>> adj;
vector<set<int>> bicomp;
int dfn[MAX_N + 1], low[MAX_N + 1];
int parent[MAX_N + 1];
bool vis[MAX_N + 1];
int n, m, num;

struct Edge {
    int u, v;
};
stack<Edge> st;

void read() {
    fin >> n >> m;
    adj = vector<vector<int>>(n + 1);
    int x, y;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        dfn[i] = parent[i] = -1;
        low[i] = INF; vis[i] = 0;
    }
}

void process_comp(int u, int v) {
    if (!st.empty()) {
        set<int> comp;
        while ((st.top().u != u || st.top().v != v) &&
               (st.top().u != v || st.top().v != u)) {
            comp.insert(st.top().u);
            comp.insert(st.top().v);
            st.pop();
        }
        comp.insert(st.top().u);
        comp.insert(st.top().v);
        st.pop();
        bicomp.push_back(comp);
    }
}

void process_rem_comp() {
    if (!st.empty()) {
        set<int> comp;
        while (!st.empty()) {
            comp.insert(st.top().u);
            comp.insert(st.top().v);
            st.pop();
        }
        bicomp.push_back(comp);
    }
}

void dfs(int vertex) {
    dfn[vertex] = low[vertex] = ++num;
    vis[vertex] = 1;
    int child = 0;
    for (int x : adj[vertex]) {
        if (!vis[x]) {
            st.push({vertex, x});
            parent[x] = vertex;
            child++;
            dfs(x);
            low[vertex] = min(low[vertex], low[x]);
            if (parent[vertex] == -1 && child >= 2)
                process_comp(vertex, x);
            if (parent[vertex] != -1 && low[x] >= dfn[vertex])
                process_comp(vertex, x);
        } else {
            if (parent[vertex] != x && low[vertex] > dfn[x]) {
                // [vertex, x] - muchie de intoarcere / back edge
                low[vertex] = dfn[x];
                st.push({vertex, x});
            }
        }
    }
}

void biconnected_comp() {
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            num = 0; dfs(i);
            process_rem_comp();
        }
}

void print_bicomp() {
    fout << (int)bicomp.size() << "\n";
    for (int i = 0; i < (int)bicomp.size(); i++) {
        for (int vertex : bicomp[i])
            fout << vertex << " ";
        fout << "\n";
    }
}

int main() {
    read(); init();
    biconnected_comp();
    print_bicomp();
    
    fin.close();
    fout.close();
    return 0;
}