結果

問題 No.3024 全単射的
ユーザー 👑 p-adic
提出日時 2024-05-27 09:56:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,296 ms / 5,000 ms
コード長 1,482 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 204,744 KB
最終ジャッジ日時 2024-12-20 20:30:11
合計ジャッジ時間 14,720 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import queue
R=range
def HopcroftKarp(S,T,edge):
	unchosen_source=set(R(S))
	prev=[-1]*T
	chosen_source=[0]*S
	chosen_target=[0]*T
	chosen_edge=[{}for s in R(S)]
	depth=[0]*(1+S+T)
	depth_min=-1
	root=[0]*(S+T)
	new_chosen_target=[0]
	while len(new_chosen_target):
		new_chosen_target=[]
		V=queue.Queue()
		D=[-1]*(1+S+T)
		last=D[:]
		D[0]=found=0
		for s in unchosen_source:V.put(1+s);D[1+s],last[1+s]=1,0
		while V.qsize():
			v=V.get()
			w=last[v]
			E=[]
			if v>S:
				s=prev[v-1-S]
				if 1+s:E=[1+s]
			else:E+=[1+S+t for t in edge[v-1]]
			for u in E:
				if D[u]<0:V.put(u);D[u],last[u]=D[v]+1,v;
			if found and D[v]>depth_min:break
			root[v-1]=root[w-1]if w else v-1
			if D[v]&1<1:
				t=v-1-S
				if chosen_target[t]<1:
					s=root[v-1]
					if chosen_source[s]<1:
						chosen_source[s]=chosen_target[t]=1;new_chosen_target+=[v]
						if found<1:found,depth_min=1,D[v]
		for nct in new_chosen_target:
			p,i=[last[nct],nct],0
			while p[0]:
				s,t=p[i]-1,p[i^1]-1-S
				if t in chosen_edge[s]:chosen_edge[s][t]^=1
				else:chosen_edge[s][t]=1
				if chosen_edge[s][t]:prev[t]=s
				p,i=[last[p[0]],p[0]],i^1
			unchosen_source.remove(p[1]-1)
	return[[prev[t],t]for t in R(T)if 1+prev[t]]
def CoordinateCompressA(A):
	Z={}
	for X in A:
		for i in R(len(X)):
			if X[i] in Z:X[i]=Z[X[i]]
			else:Z[X[i]]=X[i]=len(Z)
	return len(Z)
J=lambda:map(int,input().split())
N,M=J()
edge=[list(J())for i in R(N)]
M=CoordinateCompressA(edge)
print(len(HopcroftKarp(N,M,edge)))
0