Source code for titan_pylib.graph.flow.bipartite_max_matching

 1from titan_pylib.graph.flow.max_flow_dinic import MaxFlowDinic
 2
 3

[docs]
 4class BipartiteMaxMatching:
 5
 6    def __init__(self, n: int, m: int) -> None:
 7        """二部グラフの最大マッチングを求めるグラフを初期化します。
 8
 9        Args:
10            n (int): 左側の頂点数です。
11            m (int): 右側の頂点数です。
12        """
13        self.n = n
14        self.m = m
15        self.s = n + m
16        self.t = n + m + 1
17        self.mf = MaxFlowDinic(n + m + 2)
18        for i in range(n):
19            self.mf.add_edge(self.s, i, 1)
20        for i in range(m):
21            self.mf.add_edge(n + i, self.t, 1)
22

[docs]
23    def add_edge(self, l: int, r: int) -> None:
24        """左側の頂点 ``l`` と右側の頂点 ``r`` に辺を貼ります。
25
26        Args:
27            l (int):
28            r (int):
29        """
30        assert 0 <= l < self.n
31        assert 0 <= r < self.m
32        self.mf.add_edge(l, self.n + r, 1)

33

[docs]
34    def max_matching(self) -> tuple[int, list[tuple[int, int]]]:
35        """最大マッチングを求め、マッチングの個数と使用する辺を返します。
36        :math:`O(E \sqrt{V})` です。
37
38        Returns:
39            tuple[int, list[tuple[int, int]]]:
40        """
41        ans = self.mf.max_flow(self.s, self.t)
42        K = []
43        for a in range(self.n):
44            for b, _, _, f in self.mf.G[a]:
45                if self.n <= b < self.n + self.t and f > 0:
46                    K.append((a, b - self.n))
47        return ans, K