Transversal matroid （横断マトロイド）
(combinatorial_opt/matroids/transversal_matroid.hpp)

• View this file on GitHub
• Last update: 2022-01-08 20:23:44+09:00
• Include: #include "combinatorial_opt/matroids/transversal_matroid.hpp"

頂点集合 $U, V$，辺集合 $E$ からなる二部グラフ $G = (U, V, E)$ について定義されるマトロイド．台集合は $U$．$U$ の部分集合の独立性を，「その集合を被覆するようなマッチングが存在すること」で定義する．

計算量は，$|U| + |V| = n, |E| = m$ とすると，独立集合 $I \subset U$ の設定（set()）が $O((n + m) \sqrt{n})$，$I + {e}$ に対するサーキットの取得（circuit()）がクエリあたり $O(n + m)$．

使用例

int U = 4, V = 2;
vector<pair<int, int>> edges;
edges.emplace_back(0, 0); // 0 <= u < U, 0 <= v < V
edges.emplace_back(1, 0);
edges.emplace_back(2, 1);

TransversalMatroid M1(U, V, edges);
vector<bool> I{1, 0, 0, 0};
M1.set(I);
vector<int> a = M1.circuit(1); // [0, 1]
vector<int> b = M1.circuit(2); // [] (I + {2} is still independent)

問題例

• 2021 ICPC Asia Taiwan Online Programming Contest I. ICPC Kingdom - Codeforces 横断マトロイドとグラフマトロイドの重み付き交差．

リンク

• 離散最適化基礎論 第 6回 マトロイドに対する貪欲アルゴリズム

Depends on

• Bipartite matching (Hopcroft–Karp) (graph/bipartite_matching.hpp)
• Dulmage–Mendelsohn decomposition （DM 分解） (graph/dulmage_mendelsohn_decomposition.hpp)
• graph/strongly_connected_components.hpp

Code

#pragma once
#include "../../graph/dulmage_mendelsohn_decomposition.hpp"
#include <vector>

struct TransversalMatroid {
    int M, W;
    std::vector<std::vector<int>> to;
    TransversalMatroid(int M_, int Mopp, const std::vector<std::pair<int, int>> &edges_)
        : M(M_), W(Mopp), to(M_) {
        for (auto p : edges_) to[p.first].push_back(p.second);
    }

    int size() const { return M; }

    std::vector<int> is_opp_fixed;
    std::vector<std::vector<int>> _to_dfs;
    template <class State = std::vector<bool>> void set(State I) {
        std::vector<std::pair<int, int>> edges;

        for (int e = 0; e < M; ++e) {
            if (I[e]) {
                for (int w : to[e]) edges.emplace_back(e, w);
            }
        }
        auto dm = dulmage_mendelsohn(M, W, edges);
        is_opp_fixed.assign(W, 1);
        for (auto w : dm.front().second) is_opp_fixed[w] = 0;

        _to_dfs.assign(M + W, {});
        for (int e = 0; e < int(to.size()); ++e) {
            for (int w : to[e]) _to_dfs[e].push_back(M + w);
        }
        for (const auto &p : dm) {
            const auto &es = p.first, &ws = p.second;
            for (int i = 0; i < std::min<int>(es.size(), ws.size()); ++i) {
                _to_dfs[M + ws[i]].push_back(es[i]);
            }
        }
    }

    std::vector<int> circuit(int e) const {
        for (int w : to[e]) {
            if (!is_opp_fixed[w]) return {};
        }
        std::vector<int> vis(M + W);
        std::vector<int> st{e};
        vis[e] = 1;
        while (st.size()) {
            int now = st.back();
            st.pop_back();
            for (auto nxt : _to_dfs[now]) {
                if (vis[nxt] == 0) {
                    vis[nxt] = 1;
                    st.push_back(nxt);
                }
            }
        }
        std::vector<int> ret;
        for (int e = 0; e < M; ++e) {
            if (vis[e]) ret.push_back(e);
        }
        return ret;
    }
};

#line 2 "graph/bipartite_matching.hpp"
#include <cassert>
#include <iostream>
#include <vector>

// Bipartite matching of undirected bipartite graph (Hopcroft-Karp)
// https://ei1333.github.io/luzhiled/snippets/graph/hopcroft-karp.html
// Comprexity: O((V + E)sqrtV)
// int solve(): enumerate maximum number of matching / return -1 (if graph is not bipartite)
struct BipartiteMatching {
    int V;
    std::vector<std::vector<int>> to; // Adjacency list
    std::vector<int> dist;            // dist[i] = (Distance from i'th node)
    std::vector<int> match;           // match[i] = (Partner of i'th node) or -1 (No parter)
    std::vector<int> used, vv;
    std::vector<int> color; // color of each node(checking bipartition): 0/1/-1(not determined)

    BipartiteMatching() = default;
    BipartiteMatching(int V_) : V(V_), to(V_), match(V_, -1), used(V_), color(V_, -1) {}

    void add_edge(int u, int v) {
        assert(u >= 0 and u < V and v >= 0 and v < V and u != v);
        to[u].push_back(v);
        to[v].push_back(u);
    }

    void _bfs() {
        dist.assign(V, -1);
        std::vector<int> q;
        int lq = 0;
        for (int i = 0; i < V; i++) {
            if (!color[i] and !used[i]) q.push_back(i), dist[i] = 0;
        }

        while (lq < int(q.size())) {
            int now = q[lq++];
            for (auto nxt : to[now]) {
                int c = match[nxt];
                if (c >= 0 and dist[c] == -1) q.push_back(c), dist[c] = dist[now] + 1;
            }
        }
    }

    bool _dfs(int now) {
        vv[now] = true;
        for (auto nxt : to[now]) {
            int c = match[nxt];
            if (c < 0 or (!vv[c] and dist[c] == dist[now] + 1 and _dfs(c))) {
                match[nxt] = now, match[now] = nxt;
                used[now] = true;
                return true;
            }
        }
        return false;
    }

    bool _color_bfs(int root) {
        color[root] = 0;
        std::vector<int> q{root};
        int lq = 0;
        while (lq < int(q.size())) {
            int now = q[lq++], c = color[now];
            for (auto nxt : to[now]) {
                if (color[nxt] == -1) {
                    color[nxt] = !c, q.push_back(nxt);
                } else if (color[nxt] == c) {
                    return false;
                }
            }
        }
        return true;
    }

    int solve() {
        for (int i = 0; i < V; i++) {
            if (color[i] == -1 and !_color_bfs(i)) return -1;
        }
        int ret = 0;
        while (true) {
            _bfs();
            vv.assign(V, false);
            int flow = 0;
            for (int i = 0; i < V; i++) {
                if (!color[i] and !used[i] and _dfs(i)) flow++;
            }
            if (!flow) break;
            ret += flow;
        }
        return ret;
    }

    template <class OStream> friend OStream &operator<<(OStream &os, const BipartiteMatching &bm) {
        os << "{N=" << bm.V << ':';
        for (int i = 0; i < bm.V; i++) {
            if (bm.match[i] > i) os << '(' << i << '-' << bm.match[i] << "),";
        }
        return os << '}';
    }
};
#line 2 "graph/strongly_connected_components.hpp"
#include <algorithm>
#line 5 "graph/strongly_connected_components.hpp"

// CUT begin
// Directed graph library to find strongly connected components （強連結成分分解）
// 0-indexed directed graph
// Complexity: O(V + E)
struct DirectedGraphSCC {
    int V; // # of Vertices
    std::vector<std::vector<int>> to, from;
    std::vector<int> used; // Only true/false
    std::vector<int> vs;
    std::vector<int> cmp;
    int scc_num = -1;

    DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {}

    void _dfs(int v) {
        used[v] = true;
        for (auto t : to[v])
            if (!used[t]) _dfs(t);
        vs.push_back(v);
    }
    void _rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v])
            if (!used[t]) _rdfs(t, k);
    }

    void add_edge(int from_, int to_) {
        assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V);
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    // Detect strongly connected components and return # of them.
    // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed)
    int FindStronglyConnectedComponents() {
        used.assign(V, false);
        vs.clear();
        for (int v = 0; v < V; v++)
            if (!used[v]) _dfs(v);
        used.assign(V, false);
        scc_num = 0;
        for (int i = (int)vs.size() - 1; i >= 0; i--)
            if (!used[vs[i]]) _rdfs(vs[i], scc_num++);
        return scc_num;
    }

    // Find and output the vertices that form a closed cycle.
    // output: {v_1, ..., v_C}, where C is the length of cycle,
    //         {} if there's NO cycle (graph is DAG)
    int _c, _init;
    std::vector<int> _ret_cycle;
    bool _dfs_detectcycle(int now, bool b0) {
        if (now == _init and b0) return true;
        for (auto nxt : to[now])
            if (cmp[nxt] == _c and !used[nxt]) {
                _ret_cycle.emplace_back(nxt), used[nxt] = 1;
                if (_dfs_detectcycle(nxt, true)) return true;
                _ret_cycle.pop_back();
            }
        return false;
    }
    std::vector<int> DetectCycle() {
        int ns = FindStronglyConnectedComponents();
        if (ns == V) return {};
        std::vector<int> cnt(ns);
        for (auto x : cmp) cnt[x]++;
        _c = std::find_if(cnt.begin(), cnt.end(), [](int x) { return x > 1; }) - cnt.begin();
        _init = std::find(cmp.begin(), cmp.end(), _c) - cmp.begin();
        used.assign(V, false);
        _ret_cycle.clear();
        _dfs_detectcycle(_init, false);
        return _ret_cycle;
    }

    // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all
    // vertices belonging to the same component(The resultant graph is DAG).
    DirectedGraphSCC GenerateTopologicalGraph() {
        DirectedGraphSCC newgraph(scc_num);
        for (int s = 0; s < V; s++)
            for (auto t : to[s]) {
                if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]);
            }
        return newgraph;
    }
};

// 2-SAT solver: Find a solution for  `(Ai v Aj) ^ (Ak v Al) ^ ... = true`
// - `nb_sat_vars`: Number of variables
// - Considering a graph with `2 * nb_sat_vars` vertices
// - Vertices [0, nb_sat_vars) means `Ai`
// - vertices [nb_sat_vars, 2 * nb_sat_vars) means `not Ai`
struct SATSolver : DirectedGraphSCC {
    int nb_sat_vars;
    std::vector<int> solution;
    SATSolver(int nb_variables = 0)
        : DirectedGraphSCC(nb_variables * 2), nb_sat_vars(nb_variables), solution(nb_sat_vars) {}
    void add_x_or_y_constraint(bool is_x_true, int x, bool is_y_true, int y) {
        assert(x >= 0 and x < nb_sat_vars);
        assert(y >= 0 and y < nb_sat_vars);
        if (!is_x_true) x += nb_sat_vars;
        if (!is_y_true) y += nb_sat_vars;
        add_edge((x + nb_sat_vars) % (nb_sat_vars * 2), y);
        add_edge((y + nb_sat_vars) % (nb_sat_vars * 2), x);
    }
    // Solve the 2-SAT problem. If no solution exists, return `false`.
    // Otherwise, dump one solution to `solution` and return `true`.
    bool run() {
        FindStronglyConnectedComponents();
        for (int i = 0; i < nb_sat_vars; i++) {
            if (cmp[i] == cmp[i + nb_sat_vars]) return false;
            solution[i] = cmp[i] > cmp[i + nb_sat_vars];
        }
        return true;
    }
};
#line 5 "graph/dulmage_mendelsohn_decomposition.hpp"
#include <utility>
#line 7 "graph/dulmage_mendelsohn_decomposition.hpp"

// Dulmage–Mendelsohn (DM) decomposition （DM 分解）
// return: [(W+0, W-0), (W+1,W-1),...,(W+(k+1), W-(k+1))]
//         : sequence of pair (left vetrices, right vertices)
//         - |W+0| < |W-0| or both empty
//         - |W+i| = |W-i| (i = 1, ..., k)
//         - |W+(k+1)| > |W-(k+1)| or both empty
//         - W is topologically sorted
// Example:
// (2, 2, [(0,0), (0,1), (1,0)]) => [([],[]),([0,],[1,]),([1,],[0,]),([],[]),]
// Complexity: O(N + (N + M) sqrt(N))
// Verified: https://yukicoder.me/problems/no/1615
std::vector<std::pair<std::vector<int>, std::vector<int>>>
dulmage_mendelsohn(int L, int R, const std::vector<std::pair<int, int>> &edges) {
    for (auto p : edges) {
        assert(0 <= p.first and p.first < L);
        assert(0 <= p.second and p.second < R);
    }

    BipartiteMatching bm(L + R);
    for (auto p : edges) bm.add_edge(p.first, L + p.second);
    bm.solve();

    DirectedGraphSCC scc(L + R);
    for (auto p : edges) scc.add_edge(p.first, L + p.second);
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= L) scc.add_edge(bm.match[l], l);
    }

    int nscc = scc.FindStronglyConnectedComponents();
    std::vector<int> cmp_map(nscc, -2);

    std::vector<int> vis(L + R);
    std::vector<int> st;
    for (int c = 0; c < 2; ++c) {
        std::vector<std::vector<int>> to(L + R);
        auto color = [&L](int x) { return x >= L; };
        for (auto p : edges) {
            int u = p.first, v = L + p.second;
            if (color(u) != c) std::swap(u, v);
            to[u].push_back(v);
            if (bm.match[u] == v) to[v].push_back(u);
        }
        for (int i = 0; i < L + R; ++i) {
            if (bm.match[i] >= 0 or color(i) != c or vis[i]) continue;
            vis[i] = 1, st = {i};
            while (!st.empty()) {
                int now = st.back();
                cmp_map[scc.cmp[now]] = c - 1;
                st.pop_back();
                for (int nxt : to[now]) {
                    if (!vis[nxt]) vis[nxt] = 1, st.push_back(nxt);
                }
            }
        }
    }

    int nset = 1;
    for (int n = 0; n < nscc; ++n) {
        if (cmp_map[n] == -2) cmp_map[n] = nset++;
    }
    for (auto &x : cmp_map) {
        if (x == -1) x = nset;
    }
    nset++;

    std::vector<std::pair<std::vector<int>, std::vector<int>>> groups(nset);

    for (int l = 0; l < L; ++l) {
        if (bm.match[l] < 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
        groups[c].second.push_back(bm.match[l] - L);
    }
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
    }
    for (int r = 0; r < R; ++r) {
        if (bm.match[L + r] >= 0) continue;
        int c = cmp_map[scc.cmp[L + r]];
        groups[c].second.push_back(r);
    }

    return groups;
}
#line 4 "combinatorial_opt/matroids/transversal_matroid.hpp"

struct TransversalMatroid {
    int M, W;
    std::vector<std::vector<int>> to;
    TransversalMatroid(int M_, int Mopp, const std::vector<std::pair<int, int>> &edges_)
        : M(M_), W(Mopp), to(M_) {
        for (auto p : edges_) to[p.first].push_back(p.second);
    }

    int size() const { return M; }

    std::vector<int> is_opp_fixed;
    std::vector<std::vector<int>> _to_dfs;
    template <class State = std::vector<bool>> void set(State I) {
        std::vector<std::pair<int, int>> edges;

        for (int e = 0; e < M; ++e) {
            if (I[e]) {
                for (int w : to[e]) edges.emplace_back(e, w);
            }
        }
        auto dm = dulmage_mendelsohn(M, W, edges);
        is_opp_fixed.assign(W, 1);
        for (auto w : dm.front().second) is_opp_fixed[w] = 0;

        _to_dfs.assign(M + W, {});
        for (int e = 0; e < int(to.size()); ++e) {
            for (int w : to[e]) _to_dfs[e].push_back(M + w);
        }
        for (const auto &p : dm) {
            const auto &es = p.first, &ws = p.second;
            for (int i = 0; i < std::min<int>(es.size(), ws.size()); ++i) {
                _to_dfs[M + ws[i]].push_back(es[i]);
            }
        }
    }

    std::vector<int> circuit(int e) const {
        for (int w : to[e]) {
            if (!is_opp_fixed[w]) return {};
        }
        std::vector<int> vis(M + W);
        std::vector<int> st{e};
        vis[e] = 1;
        while (st.size()) {
            int now = st.back();
            st.pop_back();
            for (auto nxt : _to_dfs[now]) {
                if (vis[nxt] == 0) {
                    vis[nxt] = 1;
                    st.push_back(nxt);
                }
            }
        }
        std::vector<int> ret;
        for (int e = 0; e < M; ++e) {
            if (vis[e]) ret.push_back(e);
        }
        return ret;
    }
};

Back to top page