School Dance - Graph Construction

Create nodes: source $s$, $n$ boys, $m$ girls, sink $t$. Edges:

$1.$ $(s, \text{boy}_i)$ with capacity $1$ for each boy.

$2.$ $(\text{boy}_i, \text{girl}_j)$ with capacity $1$ if boy $i$ likes girl $j$.

$3.$ $(\text{girl}_j, t)$ with capacity $1$ for each girl.

Max flow through this network equals the maximum number of pairs. Each unit of flow represents one pair dancing together. The capacity $1$ ensures each person dances at most once.