二部グラフ最大マッチング

Question

グラフが初めてです。私は二部グラフに二つのセットを持っています。私はすべての可能な組み合わせの一意の一致を見つける必要があります。だから私は最大のマッチングを見つけるためにホプクロフト・カルプを使うと思った。初心者であることから、結果として一致するグラフが得られると思っていましたが、それは私に42と言います。ああ、それは本当に役立ちます。どのくらいのマッチがあるのか​​を知る必要はありません。自分自身のユニークなマッチングを知る必要があります。

何か不足していますか？結果の一致を得るにはどうすればよいですか？

Answer 1

私はHopcroft-Karpマッチ関数によって生成されたデータ構造をチェックしておらず、retrun値だけをチェックしていませんでした。戻り値はマッチの数です。しかし、Pythonコードにはself.pair辞書もありました。ペア辞書には「両側」からのマッチが含まれていますので、私の質問に答えることができます。