Cod sursa(job #3364728)

Utilizator TincaMateiTinca Matei TincaMatei Data 9 septembrie 2026 20:15:45
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>

const int MAX_N = 500001;
const int MAX_M = 500001;

int height[MAX_N], vmin[MAX_N];
std::vector<int> st;

std::vector<int> graph[MAX_N];

struct Edge {
    int a, b;
    
    int other(int x) {
        return a ^ b ^ x;
    }
};

Edge edges[MAX_M];

std::vector<std::vector<int>> bccs;

void dfs(int node, int parent_edge) {
    for (auto it : graph[node]) {
        int son = edges[it].other(node);

        if (height[son] == 0) {
            st.push_back(it);
            height[son] = vmin[son] = height[node] + 1;
            dfs(son, it);
            vmin[node] = std::min(vmin[node], vmin[son]);

            if (vmin[son] >= height[node]) {
                std::vector<int> bcc;
                int x;
                do {
                    x = st.back();
                    bcc.push_back(edges[x].a);
                    bcc.push_back(edges[x].b);
                    st.pop_back();
                } while (x != it);

                std::sort(bcc.begin(), bcc.end());
                bcc.resize(std::unique(bcc.begin(), bcc.end()) - bcc.begin());

                bccs.push_back(bcc);
            }
        } else if (it != parent_edge)
            vmin[node] = std::min(vmin[node], vmin[son]);
    }
}

int main() {

    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    int N; std::cin >> N;
    int M; std::cin >> M;
    
    for (int i = 0; i < M; i++) {
        int a; std::cin >> a;
        int b; std::cin >> b;
        
        edges[i] = {a, b};

        graph[a].push_back(i);
        graph[b].push_back(i);
    }

    for (int i = 1; i <= N; i++) 
        if (height[i] == 0) {
            height[i] = 1;
            dfs(i, -1);

            if (graph[i].size() == 0)
                bccs.push_back({i});
        }

    std::cout << bccs.size() << "\n";
    for (auto bcc : bccs) {
        // std::cout << bcc.size() << " ";
        for (auto it : bcc)
            std::cout << it << " ";
        std::cout << "\n";
    }

    return 0;
}