Skip to content

General Matching Hot Sheet

Use this sheet when the statement is really one unweighted maximum matching on a general undirected graph and odd cycles are no longer optional details.

Do Not Use When

Choose By Signal

  • arbitrary undirected graph + maximize number of disjoint edges -> Edmonds Blossom / General Matching
  • bipartite compatibility graph + cardinality only -> Matching hot sheet
  • dense square row/column assignment cost matrix -> Hungarian hot sheet
  • story is really minimum edge cover on a general graph -> often n - maximum_matching, compare QBFLOWER

Core Invariants

  • match[v] always describes a legal matching partner or -1
  • the alternating search forest is rooted at one exposed vertex
  • base[v] stores the current blossom representative after contractions
  • shrinking one blossom preserves whether an augmenting path exists
  • one successful augmentation increases the matching size by exactly 1

Main Traps

  • trying to force Hopcroft-Karp onto a non-bipartite graph
  • forgetting this lane is unweighted only
  • messing up 0-based output when the judge wants 1-based pairs
  • confusing a maximal matching with a maximum matching

Exact Starter Route

Reopen Paths