hopcroft_karp.py

from collections import defaultdict

class HopcroftKarp:
    def __init__(self, graph):
        self.graph = graph
        self.matching = {}
        self.visited = set()
        
    def bipartite_matching(self):
        for u in self.graph.keys():
            if u not in self.matching:
                self.visited = set()
                if self.dfs(u):
                    self.visited.clear()
                    
        return self.matching
    
    def dfs(self, u):
        if u in self.visited:
            return False
        self.visited.add(u)
        
        for v in self.graph[u]:
            if v not in self.matching or self.dfs(self.matching[v]):
                self.matching[u] = v
                self.matching[v] = u
                return True
        return False

# Example usage:
graph = {
    'A': ['X', 'Y'],
    'B': ['X'],
    'C': ['Y'],
    'D': []
}

hk = HopcroftKarp(graph)
matching = hk.bipartite_matching()
print(matching)