Problem p02925 (python)

Fixed submission:
n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)+5]

for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])

calced=[False]*(nedge+5)
visited=[False]*(nedge+5)
dp=[0]*nedge

def dfs(v):
	if visited[v]:
		if not calced[v]:
			return -1
		return dp[v]
	
	visited[v]=True
	dp[v]=1
	for u in g[v]:
		ret = dfs(u)
		if ret == -1:
			return -1
		dp[v] = max(dp[v],ret+1)
	
	calced[v]=True
	return dp[v]

ans = 0
for i in range(nedge):
	res = dfs(i)
	if res==-1:
		print(-1)
		exit()
	ans = max(ans,res)
print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]

for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])

calced=[False]*nedge
visited=[False]*nedge
dp=[0]*nedge

def dfs(v):
	if visited[v]:
		if not calced[v]:
			return -1
		return dp[v]
	
	visited[v]=True
	dp[v]=1
	for u in g[v]:
		ret = dfs(u)
		if ret == -1:
			return -1
		dp[v] = max(dp[v],ret+1)
	
	calced[v]=True
	return dp[v]

ans = 0
for i in range(nedge):
	res = dfs(i)
	if res==-1:
		print(-1)
		exit()
	ans = max(ans,res)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
sj = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
			sj.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

if len(ans)!=n*(n-1)//2:
	print(-1)
	exit()

dp = [[0]*n for _ in range(n)]
def dfs(x,y):
	if dp[x][y]:
		return dp[x][y]
	if g[x][y]==[]:
		dp[x][y]=1
		return dp[x][y]
	for e in g[x][y]:
		dp[x][y] = max(dfs(e[0],e[1])+1,dp[x][y])
	return dp[x][y]
maxx = 0
for edge in sj:
	maxx = max(maxx,dfs(edge[0],edge[1]))
print(maxx)