結果

問題 No.1865 Make Cycle
ユーザー ygd.ygd.
提出日時 2022-03-04 22:03:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 547 ms / 3,000 ms
コード長 1,694 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 178,636 KB
最終ジャッジ日時 2024-07-18 20:29:45
合計ジャッジ時間 7,801 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 315 ms
127,912 KB
testcase_01 AC 245 ms
118,872 KB
testcase_02 AC 381 ms
142,196 KB
testcase_03 AC 221 ms
126,952 KB
testcase_04 AC 325 ms
146,808 KB
testcase_05 AC 100 ms
90,496 KB
testcase_06 AC 339 ms
139,300 KB
testcase_07 AC 328 ms
136,424 KB
testcase_08 AC 412 ms
154,628 KB
testcase_09 AC 96 ms
90,752 KB
testcase_10 AC 359 ms
148,696 KB
testcase_11 AC 356 ms
144,816 KB
testcase_12 AC 310 ms
132,176 KB
testcase_13 AC 313 ms
129,664 KB
testcase_14 AC 273 ms
124,748 KB
testcase_15 AC 413 ms
150,464 KB
testcase_16 AC 426 ms
156,064 KB
testcase_17 AC 96 ms
85,760 KB
testcase_18 AC 104 ms
92,672 KB
testcase_19 AC 547 ms
178,636 KB
testcase_20 AC 34 ms
51,968 KB
testcase_21 AC 33 ms
51,968 KB
testcase_22 AC 35 ms
52,224 KB
testcase_23 AC 32 ms
51,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#input = sys.stdin.readline
input = sys.stdin.buffer.readline #文字列はダメ
#sys.setrecursionlimit(1000000)
#import bisect
#import itertools
#import random
#from heapq import heapify, heappop, heappush
#from collections import defaultdict 
#from collections import deque
#import copy
#import math
#from functools import lru_cache
#@lru_cache(maxsize=None)
#MOD = pow(10,9) + 7
#MOD = 998244353
#dx = [1,0,-1,0]
#dy = [0,1,0,-1]

def check(N,q,query):
    G = [[] for _ in range(N)]
    deg = [0]*N
    for i in range(q):
        a,b = query[i]
        G[a].append(b)
        deg[b] += 1

    TP = topological(G,deg)
    if len(TP) == N:
        return False
    else: #閉路があるときがTrue
        return True

def topological(graph, deg):
    start = []
    n = len(deg)
    for i in range(n):
        if deg[i] == 0: #入次数がないものがスタート
            start.append(i)
    topo = []
    while start:
        v = start.pop()
        topo.append(v)
        for u in graph[v]:
            deg[u] -= 1
            if deg[u] == 0:
                start.append(u)
    #トポロジカルソートできない場合は配列がnよりも短くなる。
    return topo


def main():
    N,Q = map(int,input().split())
    query = []
    G = [[] for _ in range(N)]
    for i in range(Q):
        a,b = map(int,input().split())
        a -= 1; b -= 1
        query.append((a,b))

    if not check(N,Q,query):
        print(-1);exit()

    ok = Q
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(N,mid,query):
            ok = mid
        else:
            ng = mid
    print(ok)

    

if __name__ == '__main__':
    main()
0