結果
問題 |
No.1865 Make Cycle
|
ユーザー |
![]() |
提出日時 | 2022-03-06 02:32:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,393 ms / 3,000 ms |
コード長 | 2,120 bytes |
コンパイル時間 | 725 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 290,796 KB |
最終ジャッジ日時 | 2024-07-03 18:13:06 |
合計ジャッジ時間 | 29,901 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
import sys input = sys.stdin.readline N,Q=map(int,input().split()) EDGE=[list(map(int,input().split())) for i in range(Q)] for i in range(Q): EDGE[i][0]-=1 EDGE[i][1]-=1 def calc(qind): E=[[] for i in range(N)] E_INV=[[] for i in range(N)] for i in range(qind): x,y=EDGE[i] E[x].append(y) E_INV[y].append(x) # DFSして帰り際にTOPに点を放り込んでいる。 # NOWで現在地点、USEINDで、どこの辺まで既に見たか、を調べている。 def Top_sort(E): Parent=[-1]*N USEIND=[0]*N TOP=[] for ROOT in range(N): if Parent[ROOT]!=-1: continue Parent[ROOT]=ROOT NOW=ROOT while NOW!=ROOT or USEIND[ROOT]!=len(E[ROOT]): if USEIND[NOW]==len(E[NOW]): TOP.append(NOW) NOW=Parent[NOW] elif E[NOW][USEIND[NOW]]==Parent[NOW]: USEIND[NOW]+=1 else: NEXT=E[NOW][USEIND[NOW]] USEIND[NOW]+=1 if Parent[NEXT]==-1: Parent[NEXT]=NOW NOW=NEXT TOP.append(ROOT) return TOP[::-1] USE=[0]*N SCC=[] # SCCを調べるための逆順DFS。 # やっていることはhttps://manabitimes.jp/math/1250 などと同じ。 def dfs2(x): Q=[x] USE[x]=1 ANS=[] while Q: x=Q.pop() ANS.append(x) for to in E_INV[x]: if USE[to]==0: USE[to]=1 Q.append(to) return ANS TOP_SORT=Top_sort(E) for x in TOP_SORT: if USE[x]==0: SCC.append(dfs2(x)) for i in range(len(SCC)): if len(SCC[i])>1: return True return False if calc(Q)==False: print(-1) else: OK=Q NG=1 while OK>NG+1: mid=(OK+NG)//2 if calc(mid)==True: OK=mid else: NG=mid print(OK)