Here is Kuhn's algorithm for School Dance:
function schoolDance(n, m, preferences):
adj = build adjacency list for boys
match = array of size m + 1, all 0 // match[girl] = boy
answer = 0
function dfs(boy, visited):
for girl in adj[boy]:
if visited[girl]:
continue
visited[girl] = true
// If girl is unmatched or her current match can find another
if match[girl] == 0 or dfs(match[girl], visited):
match[girl] = boy
return true
return false
for boy from 1 to n:
visited = array of size m + 1, all false
if dfs(boy, visited):
answer = answer + 1
// Reconstruct pairs
pairs = empty list
for girl from 1 to m:
if match[girl] != 0:
pairs.append((match[girl], girl))
print answer
print pairs
Time: . Space: .