二分图最大匹配

匈牙利算法

class Solution:
    def __init__(self):
        self.adjoin_map = {
                        '1': ['4', '8', '7'],
                        '2': ['3', '2'],
                        '3': ['4', '3'],
                        '4': ['1', '7'],
                        '5': ['1'],
                        '6': ['1'],
                        '7': ['11'],
                        '8': ['9'],
                        '9': ['11', '9']
                    }
        
    def dfs(self,l_node,adjoin_map,l_match,r_match,visited):
        for r_node in adjoin_map[l_node]:
            if r_node not in r_match:
                r_match[r_node] = l_node
                l_match[l_node] = r_node
                return True
            else:
                next_l_node = r_match[r_node]
                if next_l_node not in visited:
                    visited.add(next_l_node)
                    if self.dfs(next_l_node,adjoin_map,l_match,r_match,visited):
                        r_match[r_node] = l_node
                        l_match[l_node] = r_node
                        return True
                    else:
                        return False
                    
    def run(self):
        l_match,r_match = {},{}
        for l_node in adjoin_map.keys():
            self.dfs(l_node,self.adjoin_map,l_match,r_match,set())
        return l_match

            
if __name__ == '__main__':
    s = Solution()
    s.run()