Here is Kuhn's algorithm for maximum matching:
function maximumMatching(n, m, edges):
adj = build adjacency list for left nodes
match = array of size m + 1, all 0
function dfs(u, visited):
for v in adj[u]:
if visited[v]:
continue
visited[v] = true
if match[v] == 0 or dfs(match[v], visited):
match[v] = u
return true
return false
matchingSize = 0
for u from 1 to n:
visited = array of size m + 1, all false
if dfs(u, visited):
matchingSize = matchingSize + 1
// Reconstruct matching
pairs = empty list
for v from 1 to m:
if match[v] != 0:
pairs.append((match[v], v))
print matchingSize
print pairs
Time: . Space: .