グラフ/フロー/マッチング/Hopcroft–Karp algorithm
(test/graph/flow/matching/hopcroft-karp_algorithm.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• Hopcroft–Karp algorithm (include/emthrm/graph/flow/matching/hopcroft-karp_algorithm.hpp)

Code

/*
 * @title グラフ/フロー/マッチング/Hopcroft–Karp algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/bipartitematching
 */

#include <iostream>

#include "emthrm/graph/flow/matching/hopcroft-karp_algorithm.hpp"

int main() {
  int l, r, m;
  std::cin >> l >> r >> m;
  emthrm::HopcroftKarp hopcroft_karp(l, r);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    hopcroft_karp.add_edge(a, b);
  }
  std::cout << hopcroft_karp.solve() << '\n';
  for (int i = 0; i < l; ++i) {
    if (hopcroft_karp.match[i] != -1) {
      std::cout << i << ' ' << hopcroft_karp.match[i] - l << '\n';
    }
  }
  return 0;
}

#line 1 "test/graph/flow/matching/hopcroft-karp_algorithm.test.cpp"
/*
 * @title グラフ/フロー/マッチング/Hopcroft–Karp algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/bipartitematching
 */

#include <iostream>

#line 1 "include/emthrm/graph/flow/matching/hopcroft-karp_algorithm.hpp"



#include <algorithm>
#include <queue>
#include <vector>

namespace emthrm {

struct HopcroftKarp {
  std::vector<int> match;

  explicit HopcroftKarp(const int left, const int right)
      : match(left + right, -1), left(left), t(0), level(left),
        is_used(left, -1), graph(left) {}

  void add_edge(const int u, const int v) {
    graph[u].emplace_back(left + v);
  }

  int solve() {
    int res = 0;
    while (true) {
      std::fill(level.begin(), level.end(), -1);
      std::queue<int> que;
      for (int i = 0; i < left; ++i) {
        if (match[i] == -1) {
          que.emplace(i);
          level[i] = 0;
        }
      }
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const int dst : graph[ver]) {
          if (match[dst] != -1 && level[match[dst]] == -1) {
            level[match[dst]] = level[ver] + 1;
            que.emplace(match[dst]);
          }
        }
      }
      int tmp = 0;
      for (int i = 0; i < left; ++i) {
        if (match[i] == -1) {
          tmp += dfs(i);
          ++t;
        }
      }
      if (tmp == 0) break;
      res += tmp;
    }
    return res;
  }

 private:
  const int left;
  int t;
  std::vector<int> level, is_used;
  std::vector<std::vector<int>> graph;

  bool dfs(const int ver) {
    is_used[ver] = t;
    for (const int dst : graph[ver]) {
      const int m = match[dst];
      if (m == -1 || (is_used[m] < t && level[m] == level[ver] + 1 && dfs(m))) {
        is_used[ver] = t;
        match[ver] = dst;
        match[dst] = ver;
        return true;
      }
    }
    return false;
  }
};

}  // namespace emthrm


#line 10 "test/graph/flow/matching/hopcroft-karp_algorithm.test.cpp"

int main() {
  int l, r, m;
  std::cin >> l >> r >> m;
  emthrm::HopcroftKarp hopcroft_karp(l, r);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    hopcroft_karp.add_edge(a, b);
  }
  std::cout << hopcroft_karp.solve() << '\n';
  for (int i = 0; i < l; ++i) {
    if (hopcroft_karp.match[i] != -1) {
      std::cout << i << ' ' << hopcroft_karp.match[i] - l << '\n';
    }
  }
  return 0;
}

Back to top page