Cod sursa(job #3374554)

Utilizator badiumihneaBadiu Mihnea badiumihnea Data 9 noiembrie 2026 02:09:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <bits/stdc++.h>

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

int n, m;
std::vector<int> discovered, low;
std::vector<std::vector<int>> adj;
std::stack<std::pair<int, int>> st;
std::vector<std::vector<int>> comps;

int timer =0;

void dfs (int node, int p=0) {
    discovered[node] = low[node] = ++timer;
    for (int next :adj[node]) {
        if (next==p) {
            continue;
        }
        if (discovered[next]) {
            low[node]= std::min(low[node], discovered[next]);
            if (discovered[next]<discovered[node]) {
                st.push({node,next});
            }
        }
        else {
            st.push({node, next});
            dfs(next, node);
            low[node] = std::min(low[node], low[next]);
            if (low[next]>=discovered[node]) {
                std::vector<int> bicx;
                while (true) {
                    auto edge = st.top();
                    st.pop();
                    bicx.push_back(edge.first);
                    bicx.push_back(edge.second);
                    if (edge.first == node && edge.second == next) {
                        break;
                    }
                }

                std::sort(bicx.begin(), bicx.end());
                bicx.erase(unique(bicx.begin(), bicx.end()), bicx.end());
                comps.push_back(bicx);
            }
        }
    }
}

int main() {
    fin>>n>>m;
    adj.resize(n+1);
    discovered.assign(n+1, 0);
    low.resize(n+1);
    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 (!discovered[i]) {
            dfs(i);
        }
    }

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

    for (const auto& comp : comps) {
        for (int node : comp) {
            fout<<node << " ";
        }
        fout<<"\n";
    }
    return 0;
}