Graph Theory37 sections · 1633 units
Open in Course

Problem - School Dance - Read Statement

(CSES link)

Go read the problem statement on CSES right now. Notice the constraints: 1n,m5001 \leq n, m \leq 500 and up to 10001000 potential pairs. This is small enough for O(VE)O(VE) Kuhn's algorithm. Pay attention to what the input gives you: the number of boys, the number of girls, and a list of valid pairs (boy index, girl index).

Your output should be the maximum matching size on the first line, followed by the actual pairs.