Bipartite Matching
(Graph/bimatching.hpp)

• View this file on GitHub
• Last update: 2024-04-26 03:18:17+09:00
• Include: #include "Graph/bimatching.hpp"

Depends on

• Random (Utility/random.hpp)

Required by

• Matroid (Algorithm/matroid.hpp)
• DM decomposition (Graph/dmdecomp.hpp)

Verified with

• Verify/LC_bipartitematching.test.cpp

Code

#pragma once
#include "Utility/random.hpp"


vector<int> BiMatching(int n, int m, vector<vector<int>> &g) {
    rep(v, 0, n) Random::shuffle(ALL(g[v]));
    vector<int> L(n, -1), R(m, -1);
    for (;;) {
        vector<int> par(n, -1), root(n, -1);
        queue<int> que;
        rep(i, 0, n) if (L[i] == -1) {
            que.push(i);
            root[i] = i;
        }
        bool upd = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            if (L[root[v]] != -1)
                continue;
            for (auto u : g[v]) {
                if (R[u] == -1) {
                    while (u != -1) {
                        R[u] = v;
                        swap(L[v], u);
                        v = par[v];
                    }
                    upd = 1;
                    break;
                }
                int to = R[u];
                if (par[to] == -1) {
                    root[to] = root[v];
                    par[to] = v;
                    que.push(to);
                }
            }
        }
        if (!upd)
            break;
    }
    return L;
}

/**
 * @brief Bipartite Matching
 */

#line 2 "Utility/random.hpp"

namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
    return randgen();
}
template <typename T> T get(T L) { // [0,L]

    return get() % (L + 1);
}
template <typename T> T get(T L, T R) { // [L,R]

    return get(R - L) + L;
}
double uniform() {
    return double(get(1000000000)) / 1000000000;
}
string str(int n) {
    string ret;
    rep(i, 0, n) ret += get('a', 'z');
    return ret;
}
template <typename Iter> void shuffle(Iter first, Iter last) {
    if (first == last)
        return;
    int len = 1;
    for (auto it = first + 1; it != last; it++) {
        len++;
        int j = get(0, len - 1);
        if (j != len - 1)
            iter_swap(it, first + j);
    }
}
template <typename T> vector<T> select(int n, T L, T R) { // [L,R]

    if (n * 2 >= R - L + 1) {
        vector<T> ret(R - L + 1);
        iota(ALL(ret), L);
        shuffle(ALL(ret));
        ret.resize(n);
        return ret;
    } else {
        unordered_set<T> used;
        vector<T> ret;
        while (SZ(used) < n) {
            T x = get(L, R);
            if (!used.count(x)) {
                used.insert(x);
                ret.push_back(x);
            }
        }
        return ret;
    }
}

void relabel(int n, vector<pair<int, int>> &es) {
    shuffle(ALL(es));
    vector<int> ord(n);
    iota(ALL(ord), 0);
    shuffle(ALL(ord));
    for (auto &[u, v] : es)
        u = ord[u], v = ord[v];
}
template <bool directed, bool simple> vector<pair<int, int>> genGraph(int n) {
    vector<pair<int, int>> cand, es;
    rep(u, 0, n) rep(v, 0, n) {
        if (simple and u == v)
            continue;
        if (!directed and u > v)
            continue;
        cand.push_back({u, v});
    }
    int m = get(SZ(cand));
    vector<int> ord;
    if (simple)
        ord = select(m, 0, SZ(cand) - 1);
    else {
        rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
    }
    for (auto &i : ord)
        es.push_back(cand[i]);
    relabel(n, es);
    return es;
}
vector<pair<int, int>> genTree(int n) {
    vector<pair<int, int>> es;
    rep(i, 1, n) es.push_back({get(i - 1), i});
    relabel(n, es);
    return es;
}
}; // namespace Random


/**
 * @brief Random
 */
#line 3 "Graph/bimatching.hpp"

vector<int> BiMatching(int n, int m, vector<vector<int>> &g) {
    rep(v, 0, n) Random::shuffle(ALL(g[v]));
    vector<int> L(n, -1), R(m, -1);
    for (;;) {
        vector<int> par(n, -1), root(n, -1);
        queue<int> que;
        rep(i, 0, n) if (L[i] == -1) {
            que.push(i);
            root[i] = i;
        }
        bool upd = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            if (L[root[v]] != -1)
                continue;
            for (auto u : g[v]) {
                if (R[u] == -1) {
                    while (u != -1) {
                        R[u] = v;
                        swap(L[v], u);
                        v = par[v];
                    }
                    upd = 1;
                    break;
                }
                int to = R[u];
                if (par[to] == -1) {
                    root[to] = root[v];
                    par[to] = v;
                    que.push(to);
                }
            }
        }
        if (!upd)
            break;
    }
    return L;
}

/**
 * @brief Bipartite Matching
 */

Back to top page