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: . Space: .