結果

問題 No.1865 Make Cycle
ユーザー customaddonecustomaddone
提出日時 2022-03-05 19:37:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,245 ms / 3,000 ms
コード長 3,033 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 87,708 KB
実行使用メモリ 305,636 KB
最終ジャッジ日時 2023-09-29 09:58:49
合計ジャッジ時間 33,611 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,405 ms
288,452 KB
testcase_01 AC 954 ms
277,672 KB
testcase_02 AC 1,714 ms
295,488 KB
testcase_03 AC 758 ms
283,032 KB
testcase_04 AC 1,286 ms
296,028 KB
testcase_05 AC 1,600 ms
303,496 KB
testcase_06 AC 1,513 ms
302,332 KB
testcase_07 AC 1,364 ms
288,476 KB
testcase_08 AC 1,797 ms
296,404 KB
testcase_09 AC 1,590 ms
292,936 KB
testcase_10 AC 1,586 ms
299,400 KB
testcase_11 AC 1,633 ms
305,636 KB
testcase_12 AC 1,366 ms
290,256 KB
testcase_13 AC 1,412 ms
289,692 KB
testcase_14 AC 1,096 ms
293,284 KB
testcase_15 AC 1,696 ms
296,492 KB
testcase_16 AC 1,886 ms
296,768 KB
testcase_17 AC 1,390 ms
287,324 KB
testcase_18 AC 1,610 ms
298,636 KB
testcase_19 AC 2,245 ms
299,572 KB
testcase_20 AC 107 ms
73,196 KB
testcase_21 AC 107 ms
72,976 KB
testcase_22 AC 109 ms
73,048 KB
testcase_23 AC 110 ms
73,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right

import sys

def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getListGraph():
    return list(map(lambda x:int(x) - 1, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

mod = 10 ** 9 + 7
MOD = 998244353
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10000000)
inf = float('inf')
eps = 10 ** (-15)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

#############
# Main Code #
#############

# dfs未使用ver
def scc(E):
    n = len(E)
    # rev_Eを作成
    r_E = [[] for i in range(n)]
    for u in range(n):
        for v in E[u]:
            r_E[v].append(u)

    # トポロジカルソート
    fin = [-1] * n
    topo = []
    for u in range(n):
        if fin[u] != -1:
            continue
        stack = [u]
        while stack:
            u = stack[-1]
            if fin[u] == -1:
                fin[u] = 0
                for v in E[u]:
                    if fin[v] != -1:
                        continue
                    stack.append(v)
            else:
                stack.pop()
                if fin[u] == 0:
                    fin[u] = 1
                    topo.append(u)
    # 逆辺でdfs
    res = []
    while topo:
        u = topo.pop()
        if fin[u] != 1:
            continue
        fin[u] = 2
        cur = [u]
        i = 0
        while i < len(cur):
            u = cur[i]
            for v in r_E[u]:
                if fin[v] == 2:
                    continue
                fin[v] = 2
                cur.append(v)
            i += 1
        res.append(cur)

    g_n = len(res)
    n_e = [[] for i in range(g_n)]
    roop = [0] * g_n
    index = [0] * n
    for u in range(g_n):
        for v in res[u]:
            index[v] = u
    for u in range(N):
        for v in E[u]:
            if index[u] != index[v]:
                n_e[index[u]].append(index[v])
            else:
                roop[index[u]] = 1

    # g_n: グループの個数
    # res: グループに属する頂点は何
    # index: 頂点iはどこに属するか
    # n_e: グループ同士のエッジ
    # roop: ループするか
    return g_n, res, index, n_e, roop

"""
閉路ができるのはいつ？　有効辺
UFしていくか
"""

def f(x):
    E = [[] for i in range(N)]
    for i in range(x):
        E[edges[i][0]].append(edges[i][1])
    return max(scc(E)[4])

N, Q = getNM()
edges = [getListGraph() for i in range(Q)]
ok, ng = 0, Q
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if f(mid) == 0:
        ok = mid
    else:
        ng = mid

if f(ng) == 0:
    print(-1)
else:
    print(ng)
0