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

Question

私はグラフが初めてです。二部グラフに2つのセットがあります。可能なすべての組み合わせのユニークなマッチングを見つける必要があります。だから、私はHopcroft-Karpを使用して最大のマッチングを見つけると思った。初心者であるため、結果として一致するグラフが得られると思いましたが、それが私に言うのは42です。ああ、それは本当に役立ちます。ユニークなマッチングを知る必要があるマッチングの数を知る必要はありません。

私は何かが足りませんか？結果のマッチングを取得するにはどうすればよいですか？

Answer 1

Hopcroft-Karp Match関数によって生成されたデータストラクチャをチェックしませんでした。返品値はマッチングの数です。ただし、Pythonコードにはself.pair辞書もありましたが、ペア辞書には「両方」の側面からのマッチングが含まれており、私の質問に答えます。