結果

問題 No.1865 Make Cycle
コンテスト
ユーザー 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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