graph/others/block-cut-tree.hpp

View this file on GitHub
Last update: 2024-10-04 14:05:18+02:00
Include: #include "graph/others/block-cut-tree.hpp"
Link: https://ei1333.hateblo.jp/entry/2020/03/25/010057

Depends on

Verified with

test/aoj-3022.test.cpp

Code

#pragma once
/*
https://ei1333.hateblo.jp/entry/2020/03/25/010057
BlockCutTree: 用割点和不同的点双联通分量相连得到的树
*/
#include "../connected-components/bi-connectd-components.hpp"

template <typename T = int>
struct BlockCutTree : BiConnectedComponents<T> {
   public:
    using BiConnectedComponents<T>::BiConnectedComponents;
    using BiConnectedComponents<T>::g;
    using BiConnectedComponents<T>::articulation;
    using BiConnectedComponents<T>::bc;

    vector<int> belong;         // belong[i] 表示 i 点属于哪个组
    vector<vector<int>> group;  // group[i] 表示 i 组里包含的点
    Graph<T> tree;

    explicit BlockCutTree(const Graph<T> &g) : Graph<T>(g) {}

    int operator[](const int &k) const { return belong[k]; }

    void build() override {
        BiConnectedComponents<T>::build();
        belong.assign(g.size(), -1);
        int ptr = bc.size();
        for (auto &idx : articulation) {
            belong[idx] = ptr++;
        }
        vector<int> last(ptr, -1);  // 用于检查是否关节点和联通块已经连过边没
        tree = Graph<T>(ptr);
        for (int i = 0; i < bc.size(); i++) {
            for (auto &e : bc[i]) {
                for (auto &v : {e.from, e.to}) {
                    if (belong[v] >= (int)bc.size()) {
                        // v 是割点
                        if (exchange(last[belong[v]], i) != i) {
                            // 没和 i 连通块连过边
                            tree.add_edge(belong[v], i, e.cost);
                        }
                    } else {
                        belong[v] = i;
                    }
                }
            }
        }

        group.resize(ptr);
        for (int i = 0; i < g.size(); i++) {
            group[belong[i]].emplace_back(i);
        }
    }
};

#line 2 "graph/others/block-cut-tree.hpp"
/*
https://ei1333.hateblo.jp/entry/2020/03/25/010057
BlockCutTree: 用割点和不同的点双联通分量相连得到的树
*/
#line 2 "graph/connected-components/bi-connectd-components.hpp"
/*
点双连通：在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。
*/
#line 2 "graph/graph-template.hpp"
#include <bits/stdc++.h>
using namespace std;

template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    int idx;

    Edge() = default;

    Edge(int from, int to, T cost = 1, int idx = -1)
        : from(from), to(to), cost(cost), idx(idx) {}

    operator int() const { return to; }
};

template <typename T = int>
struct Graph {
    vector<vector<Edge<T> > > g;
    int es;

    Graph() = default;

    explicit Graph(int n) : g(n), es(0) {}

    size_t size() const { return g.size(); }

    virtual void add_directed_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es++);
    }

    // virtual 可以被重载，实现多态
    virtual void add_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }

    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if (weighted) cin >> c;
            if (directed)
                add_directed_edge(a, b, c);
            else
                add_edge(a, b, c);
        }
    }

    inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

    inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;
#line 2 "graph/others/low-link.hpp"
/*
https://oi-wiki.org/graph/cut/
割点和桥
1. 割点：对于无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
2. 极大连通分量：无向图中，能够互相到达的点在一个极大联通分量当中
3. 桥：对于无向图来说，删掉一个边后，连通分量增加了，那么这个就是桥
*/
#line 10 "graph/others/low-link.hpp"
template <typename T = int>
struct LowLink : Graph<T> {
   public:
    using Graph<T>::Graph;
    vector<int> dfn, low;      // dfn[i]: i 点的时间戳, low[i]: i 点不经过父亲能到达的最小时间戳
    vector<int> articulation;  // 存割点
    vector<Edge<T>> bridge;    // 存桥
    using Graph<T>::g;

    virtual void build() {
        vis.assign(g.size(), 0);
        dfn.assign(g.size(), 0);
        low.assign(g.size(), 0);
        inde = 0;
        for (int i = 0; i < (int)g.size(); i++) {
            if (!vis[i]) dfs(i, -1);
        }
    }

    explicit LowLink(const Graph<T> &g) : Graph<T>(g) {}

   private:
    vector<int> vis;
    int inde;

    void dfs(int u, int pre) {
        vis[u] = 1;
        dfn[u] = low[u] = inde++;
        int child = 0;
        bool is_articulation = false, beet = false;  // beet 检查是否有跟父亲的重边
        for (auto &v : g[u]) {
            if (v == pre && !exchange(beet, true)) {  // 如果 v = pre，那么第一次会被 continue 掉，而之后就会继续往下走
                continue;
            }
            if (!vis[v]) {
                child++;
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                is_articulation |= (pre >= 0 && low[v] >= dfn[u]);  // 首先这里判断的点不能是第一个进来的节点，只要有一个 v 的 low[v] >= dfn[u] 那么 u 就是割点
                if (low[v] > dfn[u]) {
                    // 如果 low[v] > dfn[u] 说明这个边是桥
                    bridge.emplace_back(v);
                }

            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }

        is_articulation |= (pre == -1 && child > 1);  // 如果它是第一个进来的点，且它有 2 个 child，那么它就是割点
        if (is_articulation) articulation.push_back(u);
    }
};
#line 7 "graph/connected-components/bi-connectd-components.hpp"

template <typename T = int>
struct BiConnectedComponents : LowLink<T> {
   public:
    using LowLink<T>::LowLink;
    using LowLink<T>::g;
    using LowLink<T>::dfn;
    using LowLink<T>::low;

    vector<vector<Edge<T>>> bc;

    void build() override {
        LowLink<T>::build();
        vis.assign(g.size(), 0);
        for (int i = 0; i < g.size(); i++) {
            if (vis[i] == 0) {
                dfs(i, -1);
            }
        }
    }

    explicit BiConnectedComponents(const Graph<T> &g) : Graph<T>(g) {}

   private:
    vector<int> vis;
    vector<Edge<T>> tmp;

    void dfs(int u, int pre) {
        vis[u] = 1;
        bool beet = false;  // beet 检查是否有跟父亲的重边
        for (auto &v : g[u]) {
            if (v == pre && exchange(beet, true) == false) continue;
            if (!vis[v] || dfn[v] < dfn[u]) {  // dfn[v] < dfn[u] 感觉只有跟父亲有重边时会加进来
                tmp.emplace_back(v);
            }

            if (!vis[v]) {
                dfs(v, u);
                if (low[v] >= dfn[u]) {
                    bc.emplace_back();
                    while (true) {
                        auto e = tmp.back();
                        bc.back().emplace_back(e);
                        tmp.pop_back();
                        if (v.idx == e.idx) break;
                    }
                }
            }
        }
    }
};
#line 7 "graph/others/block-cut-tree.hpp"

template <typename T = int>
struct BlockCutTree : BiConnectedComponents<T> {
   public:
    using BiConnectedComponents<T>::BiConnectedComponents;
    using BiConnectedComponents<T>::g;
    using BiConnectedComponents<T>::articulation;
    using BiConnectedComponents<T>::bc;

    vector<int> belong;         // belong[i] 表示 i 点属于哪个组
    vector<vector<int>> group;  // group[i] 表示 i 组里包含的点
    Graph<T> tree;

    explicit BlockCutTree(const Graph<T> &g) : Graph<T>(g) {}

    int operator[](const int &k) const { return belong[k]; }

    void build() override {
        BiConnectedComponents<T>::build();
        belong.assign(g.size(), -1);
        int ptr = bc.size();
        for (auto &idx : articulation) {
            belong[idx] = ptr++;
        }
        vector<int> last(ptr, -1);  // 用于检查是否关节点和联通块已经连过边没
        tree = Graph<T>(ptr);
        for (int i = 0; i < bc.size(); i++) {
            for (auto &e : bc[i]) {
                for (auto &v : {e.from, e.to}) {
                    if (belong[v] >= (int)bc.size()) {
                        // v 是割点
                        if (exchange(last[belong[v]], i) != i) {
                            // 没和 i 连通块连过边
                            tree.add_edge(belong[v], i, e.cost);
                        }
                    } else {
                        belong[v] = i;
                    }
                }
            }
        }

        group.resize(ptr);
        for (int i = 0; i < g.size(); i++) {
            group[belong[i]].emplace_back(i);
        }
    }
};