Cod sursa(job #3364729)

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

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

int t_global = 0;
int t_in[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) {
    ++t_global;
    vmin[node] = t_in[node] = t_global;

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

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

            if (vmin[son] >= t_in[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], t_in[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 (t_in[i] == 0) {
            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;
}