Cod sursa(job #2954316)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 13 decembrie 2022 22:37:15
Problema Componente biconexe Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#ifdef BLAT
    #include "debug/debug.hpp"
#else
    #define debug(x...)
#endif

using namespace std;

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

using Graph = vector <vector <int>>;

void append_bcc(int u, int v, vector <vector <int>> &bcc, stack <pair <int, int>> &st) {
    vector <int> comp;
    pair <int, int> top;
    do {
        top = st.top();
        comp.push_back(top.second);
        st.pop();
    } while (top != make_pair(u, v));

    if (comp.size() == 1)
        comp.push_back(u);
    bcc.push_back(comp);
}

void dfs(int node, Graph &g, vector <int> &d, vector <int> &l, 
        stack <pair <int, int>> &st, vector <vector <int>> &bcc, int parent = 0) {
    d[node] = l[node] = 1 + d[parent];

    for (auto to : g[node]) {
        if (d[to] == 0) {
            st.push(make_pair(node, to));
            dfs(to, g, d, l, st, bcc, node);

            l[node] = min(l[node], l[to]);
            if (l[to] >= d[node])
                append_bcc(node, to, bcc, st);
        } else if (to != parent) {
            if (d[to] < d[node]) {
                st.push(make_pair(node, to));
                l[node] = min(l[node], d[to]);
            }
        }
    }
}

int main() {
    int n, m;
    in >> n >> m;
    Graph g(1 + n);

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector <int> depth(1 + n), low(1 + n);
    stack <pair <int, int>> st;
    vector <vector <int>> bcc;
    dfs(1, g, depth, low, st, bcc);

    out << bcc.size() << '\n';
    for (auto comp : bcc) {
        for (auto it : comp)
            out << it << ' ';
        out << '\n';
    }
    in.close();
    out.close();
    return 0;
}