search

diegodantasf / cp-codebook

Common algorithms that I use in competitive programming
0 stars 0 forks source link

Graph/kuhn #7

Closed diegodantasf closed 2 years ago

diegodantasf commented 3 years ago

Adding Kuhn algorithm implementation for maximum matching.

Time complexity: O(V * E)

Implemented two heuristics:

  1. Random shuffle: shuffle the adjacency list
  2. Warm start: Pair up trivial pairs before running the algorithm

Problems to test the algorithm: