匈牙利算法
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()
