結果

問題 No.3024 全単射的
ユーザー detteiuu
提出日時 2025-02-14 22:55:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 874 ms / 5,000 ms
コード長 1,972 bytes
コンパイル時間 671 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 188,208 KB
最終ジャッジ日時 2025-02-14 22:55:43
合計ジャッジ時間 7,246 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

INF = 10**18

class HopcroftKarp:
    def __init__(self, N1, N2):
        self.N1 = N1
        self.N2 = N2
        self.G = [[] for _ in range(self.N1+1)]
        self.pair1 = [0]*(self.N1+1)
        self.pair2 = [0]*(self.N2+1)
        
    def add_edge(self, fr, to):
        self.G[fr].append(to)
    
    def bfs(self):
        que = deque()
        for i in range(1, self.N1+1):
            if self.pair1[i] == 0:
                self.dist[i] = 0
                que.append(i)
            else:
                self.dist[i] = INF
        self.dist[0] = INF
        while que:
            n = que.popleft()
            if self.dist[n] < self.dist[0]:
                for v in self.G[n]:
                    if self.dist[self.pair2[v]] == INF:
                        self.dist[self.pair2[v]] = self.dist[n]+1
                        que.append(self.pair2[v])
        return self.dist[0] != INF

    def dfs(self, n):
        if n != 0:
            for v in self.G[n]:
                if self.dist[self.pair2[v]] == self.dist[n]+1:
                    if self.dfs(self.pair2[v]):
                        self.pair2[v] = n
                        self.pair1[n] = v
                        return True
            self.dist[n] = INF
            return False
        return True
    
    def flow(self):
        self.dist = [0]*(self.N1+1)
        ans = 0
        while self.bfs():
            for i in range(1, self.N1+1):
                if self.pair1[i] == 0 and self.dfs(i):
                    ans += 1
        return ans

N, M = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]

def compress(A):
    S = sorted(set(A))
    D = dict()
    for i in range(len(S)):
        D[S[i]] = i
    return D

B = []
for X, Y in XY:
    B.append(X)
    B.append(Y)
D = compress(B)

H = HopcroftKarp(N, len(D))
for i, (X, Y) in enumerate(XY):
    H.add_edge(i+1, D[X]+1)
    H.add_edge(i+1, D[Y]+1)

print(H.flow())
0