Problem p02925 (python)

Fixed submission:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[-1] + [int(x) - 1 for x in row.split()][::-1] for row in readlines()]

# A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x, cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(1005)] for i in range(1005)]
V = 0
for i in range(N):
    for j in range(N):
        ids[i][j] = V
        V += 1

MAXV = 1005 * 1005 // 2

visited = [False for i in range(MAXV)]
calculated = [False for i in range(MAXV)]
dp = [0 for i in range(MAXV)]

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()

        return dp[v]

    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        dp[v] = max(dp[v], dfs(u) + 1)

    calculated[v] = True
    return dp[v]

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(N)] for i in range(N)]
V = 0
for i in range(N):
    for j in range(N):
        ids[i][j] = V
        V += 1

MAXV = 1005 * 1005 // 2

visited = [False for i in range(MAXV)]
calculated = [False for i in range(MAXV)]
dp = [0 for i in range(MAXV)]

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()

        return dp[v]

    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        dp[v] = max(dp[v], dfs(u) + 1)

    calculated[v] = True
    return dp[v]

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(N)] for i in range(N)]
V = 0
for i in range(N):
    for j in range(N):
        ids[i][j] = V
        V += 1

MAXV = 1000 * 1000 // 2

visited = [False for i in range(MAXV)]
calculated = [False for i in range(MAXV)]
dp = [0 for i in range(MAXV)]

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()

        return dp[v]

    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        dp[v] = max(dp[v], dfs(u) + 1)

    calculated[v] = True
    return dp[v]

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

l = defaultdict(list)
visited = {}
dp = {}

# make topological tree
key = ''
for i in range(n):

    if i + 1 < int(A[i][0]):
        key = '{}-{}'.format(i + 1, A[i][0])
    else:
        key = '{}-{}'.format(A[i][0], i + 1)
    
    visited[key] = False 
    dp[key] = 0 
    prev_key = key

    for j in range(1, n - 1):
        if i + 1 < int(A[i][j]):
            key = '{}-{}'.format(i + 1, A[i][j])
        else:
            key = '{}-{}'.format(A[i][j], i + 1)

        l[prev_key].append(key)
        prev_key = key
        # init visited
        visited[key] = False 
        dp[key] = 0


topo = []
# dp = [0 for i in range(n + 1)]
def dfs(start):
    if visited[start]:
        return dp[start]

    visited[start] = True    
    dp[start] = 0
    for node in l[start]:
        dp[start] = max(dp[start], dfs(node) + 1)

    return dp[start]

ans = 0
for key in list(l):
    ans = max(dfs(key), ans)

print(ans + 1)

# print(l)
# print(topo)
# for node in reversed(topo):


# for noe in topo:

Buggy submission (verdict: Runtime Error):
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

l = defaultdict(list)
visited = {}
passed = {}

# make topological tree
key = ''
for i in range(n):

    if i + 1 < int(A[i][0]):
        key = f'{i + 1}-{A[i][0]}'
    else:
        key = f'{A[i][0]}-{i + 1}'
    
    visited[key] = False 
    passed[key] = False 
    prev_key = key

    for j in range(1, n - 1):
        if i + 1 < int(A[i][j]):
            key = f'{i + 1}-{A[i][j]}'
        else:
            key = f'{A[i][j]}-{i + 1}'

        l[prev_key].append(key)
        prev_key = key
        # init visited
        visited[key] = False 
        passed[key] = False 


topo = []
def dfs(start):
    passed[start] = True
    if not l[start]:
        visited[start] = True
        topo.append(start)
        return
    
    for node in l[start]:
        if visited[node]:
            continue
        
        if passed[node]:
            print(-1)
            exit()
        dfs(node)

    visited[start] = True
    topo.append(start)

for key in list(l):
    if visited[key]:
        continue
    dfs(key)

res = 0
check = [False for i in range(n + 1)]
for node in topo:
    a, b = map(int, node.split('-'))
    if check[a] or check[b]:
        check = [False for i in range(n + 1)]
        res += 1

    check[a] = True
    check[b] = True

if any(check):
    res += 1
print(res)