結果

問題 No.1865 Make Cycle
ユーザー ygd.ygd.
提出日時 2022-03-04 22:03:01
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 701 ms / 3,000 ms
コード長 1,694 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 86,836 KB
実行使用メモリ 175,864 KB
最終ジャッジ日時 2023-09-26 01:03:53
合計ジャッジ時間 11,269 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 393 ms
128,772 KB
testcase_01 AC 304 ms
118,384 KB
testcase_02 AC 494 ms
143,464 KB
testcase_03 AC 271 ms
130,736 KB
testcase_04 AC 433 ms
150,428 KB
testcase_05 AC 141 ms
91,832 KB
testcase_06 AC 455 ms
137,260 KB
testcase_07 AC 432 ms
140,048 KB
testcase_08 AC 564 ms
152,592 KB
testcase_09 AC 137 ms
91,856 KB
testcase_10 AC 468 ms
146,112 KB
testcase_11 AC 481 ms
149,688 KB
testcase_12 AC 382 ms
131,132 KB
testcase_13 AC 404 ms
128,936 KB
testcase_14 AC 337 ms
127,844 KB
testcase_15 AC 512 ms
149,920 KB
testcase_16 AC 531 ms
157,564 KB
testcase_17 AC 136 ms
86,952 KB
testcase_18 AC 140 ms
93,588 KB
testcase_19 AC 701 ms
175,864 KB
testcase_20 AC 70 ms
71,388 KB
testcase_21 AC 72 ms
71,060 KB
testcase_22 AC 71 ms
71,052 KB
testcase_23 AC 71 ms
71,000 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