Problem p02925 (python)

Fixed submission:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]

N =n*(n-1)//2

g = [[] for i in range(N)]
p = [[] for i in range(N)]

for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
        
#print(g)
#print(p)

ans = [0]*(N)

indegree = [len(v) for v in p] # 流入辺の数を数えた配列
Source = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
#L = [] #ソート結果をためておく配列
num = 0
while Source:
    node = Source.pop()
    #L.append(node)
    num += 1
    for child in g[node]:
        indegree[child] -= 1 #辺 node -> child を削除する
        if ans[child] < ans[node]+1: ans[child] = ans[node]+1     
        if indegree[child] == 0:
            Source.append(child)

#print(num)
if num != N:
    print(-1)
else:
    print(max(ans)+1)

#print(ans)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
N =n*(n-1)//2

"""
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]
g = [[] for i in range(N)]
p = [[] for i in range(N)]
for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
"""

a = [[int(j)-1 for j in readline().split()] for i in range(n)]

g = {(i,j): [] for i in range(n) for j in range(i+1,n)}
p = {(i,j): [] for i in range(n) for j in range(i+1,n)}
for i in range(n):
    for j in range(n-2):
        if i < a[i][j]:
            ij = (i, a[i][j])
        else:
            ij = (a[i][j],i)
        if i < a[i][j+1]:
            ijj = (i, a[i][j+1])
        else:
            ijj = (a[i][j+1],i)
        g[ij].append(ijj)
        p[ijj].append(ij)


"""
トポロジカルソート
DAG なら
g: グラフの隣接行列
p: 逆辺の隣接行列

q をheapq にしたりすると、辞書順にとりだしたりとかができる。
"""
def topological_sort_queue(g,p):
#    indegree = [len(v) for v in p] # 流入辺の数を数えた配列
#    q = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
    indegree = {v:len(vc) for v,vc in p.items()} # 流入辺の数を数えた配列
    q = [i for i, c in indegree.items() if c == 0] #流入辺0の点の集合
    L = [] #ソート結果をためておく配列

    ans = {i:0 for i in g}
    a = 0
    while q:
        v = q.pop()
        L.append(v)
        for c in g[v]: #配る
            ans[c] = max(ans[c],ans[v]+1)
            a = max(a,ans[c])
            indegree[c] -= 1 #辺 node -> child を削除する
            if indegree[c] == 0:
                q.append(c)
    if len(L) != N:
#        print("サイクル検出")
        return -1
    else:
#        return(L)
        return(a+1)        

print(topological_sort_queue(g,p))

assert n != 4

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(input())
N =n*(n-1)//2

"""
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]
g = [[] for i in range(N)]
p = [[] for i in range(N)]
for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
"""

a = [[int(j)-1 for j in readline().split()] for i in range(n)]

g = {(i,j): [] for i in range(n) for j in range(i+1,n)}
p = {(i,j): [] for i in range(n) for j in range(i+1,n)}
for i in range(n):
    for j in range(n-2):
        if i < a[i][j]:
            ij = (i, a[i][j])
        else:
            ij = (a[i][j],i)
        if i < a[i][j+1]:
            ijj = (i, a[i][j+1])
        else:
            ijj = (a[i][j+1],i)
        g[ij].append(ijj)
        p[ijj].append(ij)

print(g)

"""
トポロジカルソート
DAG なら
g: グラフの隣接行列
p: 逆辺の隣接行列

q をheapq にしたりすると、辞書順にとりだしたりとかができる。
"""
def topological_sort_queue(g,p):
#    indegree = [len(v) for v in p] # 流入辺の数を数えた配列
#    q = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
    indegree = {v:len(vc) for v,vc in p.items()} # 流入辺の数を数えた配列
    q = [i for i, c in indegree.items() if c == 0] #流入辺0の点の集合
    L = [] #ソート結果をためておく配列

    ans = {i:0 for i in g}
    a = 0
    print(p)
    print(indegree)
    print(q)
    while q:
        v = q.pop()
        L.append(v)
        for c in g[v]: #配る
            ans[c] = max(ans[c],ans[v]+1)
            a = max(a,ans[c])
            indegree[c] -= 1 #辺 node -> child を削除する
            if indegree[c] == 0:
                q.append(c)
    if len(L) != N:
#        print("サイクル検出")
        return -1
    else:
#        return(L)
        return(a+1)        

print(topological_sort_queue(g,p))

assert n!=3