Graph Theory37 sections · 1633 units
Open in Course

Problem - School Dance

(CSES 1696)

CSES problem: nn boys and mm girls. Each boy lists girls he's willing to dance with. Find the maximum number of boy-girl pairs where each person dances at most once. This is maximum bipartite matching. Boys are one set, girls are the other.

Each preference is an edge. Find the maximum matching. Model it as a flow problem: source to boys (capacity 11), boys to girls (capacity 11), girls to sink (capacity 11). Max flow is the answer.