Problem p02925 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def pre_order(E):
    # 有向グラフ上の深さ優先探索(DFS)
    # NlogNくらいありそう
    N = len(E)
    order = []
    parents = [-1]*N
    seen = [-1]*N
    looped = False
    q = [i for i in range(N) if len(E[i]) == 0]
    if not q:
        # これはループがあるケースだが
        q = [0]
        looped = True

    while q:
        v = q.pop()
        order.append(v)
        seen[v] = 1
        for u in E[v]:
            if seen[u] != -1:
                looped = True
                continue
            parents[u] = v
            q.append(u)
            seen[u] = 0
    return order, parents


def main():
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            # fで書いていたけど遅いので、移す
            frm = f(i, A[i][j])
            to = f(i, A[i][j+1])
            out[frm].append(to)
    # print(out)

    # 閉路検出
    M = (N*(N-1)//2)

    order, parents, looped = pre_order(out)
    if looped:
        print(-1)
        return

    # 最長パスを得る
    # パスは自分より下位の情報が必要なので、post_orderで見る
    depth = [-1]*M
    longest = -1

    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()