Cacher is the code snippet organizer for pro developers

# 頂点集合XとYの二部グラフの最大マッチング
#   X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
# 以下のデータ構造は作成済みとする
#   :List[set]: edges[x]=xとつながるYの頂点のset

def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False
 
matched = [-1] * yn

# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(xn)))