結果

問題 No.1865 Make Cycle
コンテスト
ユーザー customaddone
提出日時 2022-03-05 19:37:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,791 ms / 3,000 ms
コード長 3,033 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 304,256 KB
最終ジャッジ日時 2024-07-22 04:32:32
合計ジャッジ時間 38,982 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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