二部グラフの最大マッチング
(graph/bipartite/bipartite_matching.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/bipartite/bipartite_matching.hpp"
• Link: https://qiita.com/drken/items/7f98315b56c95a6181a4
• Link: https://qiita.com/drken/items/e805e3f514acceb87602

概要

二部グラフの最大マッチング. 最大流で求める.

• 最大マッチングは, 最小点被覆$M$と一致.
• 最大安定集合(最大独立集合)は, 最小辺被覆と$V - M$で一致.

計算量

$O(EV)$

使用例

• bipartite_matching(g) : 二部グラフの最大マッチング.
  • マッチングの個数を返す.

Verified with

• test/aoj/GRL_7_A.test.cpp

Code

/**
 * @brief 二部グラフの最大マッチング
 * @docs docs/graph/bipartite/bipartite_matching.md
 * @see https://qiita.com/drken/items/e805e3f514acceb87602
 * @see https://qiita.com/drken/items/7f98315b56c95a6181a4
 */

template <typename T>
int bipartite_matching(const Graph<T> &g) {
    int timestamp = 0;
    vector<int> alive(g.V, 1), used(g.V, 0), match(g.V, -1);
    auto dfs = [&](auto &&f, int cur) -> bool {
        used[cur] = timestamp;
        for (auto &nxt : g.mat[cur]) {
            int w = match[nxt];
            if (alive[nxt] == 0) continue;
            if (w == -1 or (used[w] != timestamp and f(f, w))) {
                match[cur] = nxt;
                match[nxt] = cur;
                return true;
            }
        }
        return false;
    };
    int ret = 0;
    for (int i = 0; i < g.V; ++i) {
        if (alive[i] == 0) continue;
        if (match[i] == -1) {
            ++timestamp;
            ret += dfs(dfs, i);
        }
    }
    return ret;
}

#line 1 "graph/bipartite/bipartite_matching.hpp"
/**
 * @brief 二部グラフの最大マッチング
 * @docs docs/graph/bipartite/bipartite_matching.md
 * @see https://qiita.com/drken/items/e805e3f514acceb87602
 * @see https://qiita.com/drken/items/7f98315b56c95a6181a4
 */

template <typename T>
int bipartite_matching(const Graph<T> &g) {
    int timestamp = 0;
    vector<int> alive(g.V, 1), used(g.V, 0), match(g.V, -1);
    auto dfs = [&](auto &&f, int cur) -> bool {
        used[cur] = timestamp;
        for (auto &nxt : g.mat[cur]) {
            int w = match[nxt];
            if (alive[nxt] == 0) continue;
            if (w == -1 or (used[w] != timestamp and f(f, w))) {
                match[cur] = nxt;
                match[nxt] = cur;
                return true;
            }
        }
        return false;
    };
    int ret = 0;
    for (int i = 0; i < g.V; ++i) {
        if (alive[i] == 0) continue;
        if (match[i] == -1) {
            ++timestamp;
            ret += dfs(dfs, i);
        }
    }
    return ret;
}

Back to top page