Cod sursa(job #3154539)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 4 octombrie 2023 23:04:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <vector>
#include <stack>
#include <set>


const int MAX_N = 100001;

std::vector<int> adj[MAX_N];
std::vector<std::vector<int>> blockCut;

bool visited[MAX_N];
int depth[MAX_N], low[MAX_N];
std::stack<std::pair<int, int>> s;

void dfs(int u, int d) {
    depth[u] = d;
    low[u] = d;
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            s.push(std::make_pair(u, v));
            dfs(v, d + 1);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= depth[u]) {
                //std::cerr << u << " " << v << '\n';
                std::set<int> c;
                while (s.top().first != u && s.top().second != v) {
                    c.insert(s.top().first);
                    c.insert(s.top().second);
                    s.pop();
                }
                c.insert(s.top().first);
                c.insert(s.top().second);
                s.pop();
                std::vector<int> convert;
                for (int i : c)
                    convert.push_back(i);
                blockCut.push_back(convert);
            }
        } else {
            low[u] = std::min(low[u], depth[v]);
        }
    }
}


int main() {

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

    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, 0);
    std::cout << blockCut.size() << '\n';
    for (auto i : blockCut) {
        for (auto j: i)
            std::cout << j + 1 << " ";
        std::cout << '\n';
    }

    return 0;
}