Problem: N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.  The tournament is round-robin format, and there will be N(N-1)/2 matches in total. Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.    * Each player plays at most one matches in a day.   * Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Submission attempts (in order):
from collections import deque
from sys import stderr
N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]
next_index = [0] * N
nq = deque(range(N))
result = -1
finished = 0
while nq:
  result += 1
  print("day = %d" % result, file = stderr)
  q = nq
  nq = deque()
  booked = [False] * N
  while q:
    player = q.popleft()
    if booked[player]:
      continue
    if next_index[player] == N - 1:
      continue
    opponent = a[player][next_index[player]]
    if booked[opponent]:
      continue
    if a[opponent][next_index[opponent]] != player:
      continue
    print('match %d vs %d' % (player, opponent), file = stderr)
    booked[player] = True
    booked[opponent] = True
    next_index[player] += 1
    next_index[opponent] += 1
    if next_index[player] == N - 1:
      finished += 1
    if next_index[opponent] == N - 1:
      finished += 1
    nq.append(player)
    nq.append(opponent)
  if finished == N:
    break
if finished == N:
  print(result)
else:
  print(-1)


from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id = [[0] * N for _ in range(N)]

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(N):
      if i >= j:
        continue
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)


from sys import exit, setrecursionlimit
setrecursionlimit(1000000)
main()


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

    node_id_db = [[0] * (N+1) for _ in range(N + 1)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()


from sys import setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1] * (N * (N - 1) // 2)
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(10 ** 6)
main()


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted