Checklist - Bipartite Matching

Before solving a matching problem:

$1.$ Verify the graph is bipartite ($2$-coloring check).

$2.$ Identify groups $L$ and $R$.

$3.$ Build adjacency list for $L$.

$4.$ Implement Kuhn's DFS with visited array.

$5.$ Loop through $L$, count matches.

Common extensions: Check Hall's condition for perfect matching, construct minimum vertex cover via König's theorem, compute maximum independent set as complement.