School Dance - Implementation

Here is the bipartite matching implementation:

function schoolDance(n, m, preferences):
    // Node numbering: 0 = source, 1..n = boys, n+1..n+m = girls, n+m+1 = sink
    source = 0
    sink = n + m + 1
    capacity = 2D array of size (n + m + 2) x (n + m + 2), all 0
    adj = adjacency list

    // Source to boys
    for boy from 1 to n:
        capacity[source][boy] = 1
        adj[source].append(boy)
        adj[boy].append(source)

    // Boys to girls (based on preferences)
    for (boy, girl) in preferences:
        girlNode = n + girl
        capacity[boy][girlNode] = 1
        adj[boy].append(girlNode)
        adj[girlNode].append(boy)

    // Girls to sink
    for girl from 1 to m:
        girlNode = n + girl
        capacity[girlNode][sink] = 1
        adj[girlNode].append(sink)
        adj[sink].append(girlNode)

    maxFlow = edmondsKarp(n + m + 2, source, sink, capacity, adj)

    // Extract matching
    pairs = empty list
    for boy from 1 to n:
        for girlNode from n + 1 to n + m:
            if originalCapacity[boy][girlNode] == 1 and capacity[boy][girlNode] == 0:
                pairs.append((boy, girlNode - n))

    print maxFlow
    print pairs

Time: $O(VE^2)$. Space: $O(V + E)$.