Problem:


Score : 500 points

Problem Statement

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.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
As = [deque([])]
for _ in range(N):
  As.append(deque(list(map(int, input().split()))))

cnt = 0
cset = set([i for i in range(1,N+1)])
while len(cset) > 0:
  cnt += 1
  fset = set()
  nex = set([])
  f = 1
  for i in cset:
    if i not in fset:
      if As[As[i][0]][0] == i and As[i][0] not in fset:
        vis = As[i].popleft()
        fset.add(vis)
        fset.add(As[vis].popleft())
        if len(As[i]) > 0:
          nex.add(i)
        if len(As[vis]) > 0:
          nex.add(vis)
        f = 0
  cset = nex
  if f == 1:
    print('-1')
    exit()
      
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
As = [[]]
iset = [0]*(N+1)
for _ in range(N):
  As.append(list(map(int, input().split())))

cnt = 0
cset = set([i for i in range(1,N+1)])
while len(cset) > 0:
  cnt += 1
  fset = set()
  nex = set()
  f = 1
  for i in cset:
    if i not in fset:
      vis = As[i][iset[i]]
      if As[vis][iset[vis]] == i and vis not in fset:
        iset[i] += 1
        iset[vis] += 1
        fset.add(i)
        fset.add(vis)
        if iset[i] < N-1:
          nex.add(i)
        if iset[vis] < N-1:
          nex.add(vis)
        f = 0
  cset = nex
  if f == 1:
    print('-1')
    exit()
    
print(cnt)

Submission status: Accepted

Solution code:

min2 = lambda x,y: x if x < y else y

N = int(input())

queues = [list(map(lambda x: int(x)-1,input().split()))[::-1] for _ in range(N)]

q = set()
for i,l in enumerate(queues):
    if i < l[-1] and queues[l[-1]][-1] == i:
        q.add(i)

d = 0
while q:
    possible = set()
    for v in q:
        u = queues[v].pop()
        queues[u].pop()
        possible.add(v)
        possible.add(u)

    q.clear()
    for v in possible:
        try:
            u = queues[v][-1]
            if queues[u][-1] == v:
                q.add(min2(u,v))
        except IndexError:
            pass
    d += 1

print(-1 if any(l for l in queues) else d)

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    if not stacks[a]:
      return -1
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==2*N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = [ deque() for _ in range(N) ]

for i in range(N):
  for aa in list(map(int,input().split())):
    aa -= 1
    A[i].append(aa)

def check(i):
  if len(A[i])==0: return
  j = A[i][0]
  if len(A[j])==0: return

  if A[j][0] == i:
    if j<i: i,j = j,i
    q.add((i,j))

q = set()
for i in range(N):
  check(i)

ans = 0
while q:
  ans += 1

  prevq = q
  q = set()
  for p in prevq:
    i,j = p
    A[i].popleft()
    A[j].popleft()

  for p in prevq:
    i,j = p
    check(i)
    check(j)

for i in range(N):
  if len(A[i]) != 0:
    print(-1)
    exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def max2(x,y):
    return x if x > y else y

class DiGraph:
    def __init__(self, n, decrement=True, edges=[]):
        """
        incs[p]: 頂点 p に流入するリンク数
        """
        self.n = n
        self.decrement = decrement
        self.edges = [set() for _ in range(self.n)]
        self.incs = [0]*self.n
        for _from, _to in edges:
            self.add_edge(_from,_to)

    def add_edge(self, _from, _to):
        if self.decrement:
            _from -= 1
            _to -= 1
        self.edges[_from].add(_to)
        self.incs[_to] += 1

    def topological_sort_depth(self):
        """
        :return 各作業に１日かかると仮定したときに、最短で何日かかるかを返す
        """
        next_set = {p for p, inc in enumerate(self.incs) if inc == 0}
        res = []
        depth = [1]*self.n
        while next_set:
            p = next_set.pop()
            d = depth[p] + 1
            res.append(p+self.decrement)
            for q in self.edges[p]:
                self.incs[q] -= 1
                depth[q] = max2(d, depth[q])
                if self.incs[q] == 0:
                    next_set.add(q)
        if len(res) == self.n:
            return max(depth)
        else:
            return -1

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.DiGraph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()

################################################################################

N = int(input())
graph = DiGraph(N*N, decrement=True)
visited = set()
for i in range(1,N+1):
    p0 = -1
    for j in map(int, input().split()):
        p = i*N + j if j > i else j*N + i
        if p0 != -1:
            graph.add_edge(p0, p)
        p0 = p
print(graph.topological_sort_depth())

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    match = defaultdict(lambda : -1)
    for i in range(N):
        a = deque(map(lambda x: int(x)-1, input().split()))
        match[i] = a[0]
        A.append(a)
    

    ans = 0
    players = deque(range(N))

    matched = True
    while matched and len(players) > 0:
        matched = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)

        for i in players:
            if match[i] == -1:
                continue
            a = A[i]
            j = a[0]
            b = A[j]

            if match[j] == i:
                a.popleft()
                b.popleft()
                matched = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)

        players = next_players
        match.update(next_match)
        ans += 1


        
    print(ans if matched and len(next_players)==0 else -1)








    

    ans = 0

    

    
   
main()

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    match = defaultdict(lambda : -1)
    for i in range(N):
        a = deque(map(lambda x: int(x)-1, input().split()))
        match[i] = a[0]
        A.append(a)
    

    ans = 0
    players = deque(range(N))

    matched = True
    while matched and len(players) > 0:
        matched = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)

        for i in players:
            if match[i] == -1:
                continue
            a = A[i]
            j = a[0]
            b = A[j]

            if match[j] == i and match[i] == j:
                a.popleft()
                b.popleft()
                matched = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)


            else:
                next_match[i] = a[0]

        players = next_players
        match.update(next_match)
        ans += 1


        
    print(ans if matched and len(next_players)==0 else -1)








    

    ans = 0

    

    
   
main()

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = []
    for i in range(N):
        A.append(deque(map(lambda x: int(x)-1, input().split())))
    
    dbg('hoge')
    ans = 0
    players = deque(range(N))
    calc = 0
    
    match = defaultdict(lambda : -1)
    first = True
    while True:
        mathced = False
        next_players = deque()
        next_match = defaultdict(lambda : -1)
        # dbg('day',ans)
        for i in players:
            # dbg(i,ans,players,A,match)
            calc += 1
            a = A[i]
            if len(a) == 0:
                continue
            j = a[0]
            b = A[j]

            
            
            if match[j] == i and match[i] == j:
                # dbg(i,j)
                b.popleft()
                # if b[0] != i:
                #     dbg('fuga')
                a.popleft()
                mathced = True
                match[i] = -1
                match[j] = -1
                if len(a) > 0:
                    next_match[i] = a[0]
                    next_players.append(i)

                if len(b) > 0:
                    next_match[j] = b[0]
                    next_players.append(j)


            else:
                next_match[i] = a[0]

        players = next_players
        match.update(next_match)
        if first:
            dbg('hogehoge')
            first = False
            players = range(N)
            continue
        ans += 1
        if not mathced or len(players) == 0:
            break

        
    print(ans if mathced and len(next_players)==0 else -1)
    dbg(calc,mathced,len(next_players),len(a),len(b))







    

    ans = 0

    

    
   
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

graph = [[] for _ in range(N * N)]
parents = [0] * (N * N)
for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        parents[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)

q = deque()
for i, v in enumerate(parents):
    if v == 0:
        q.append(i)
        visited[i] = True
        dist[i] = 1

while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        parents[v] -= 1
        if parents[v] == 0:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

print(max(dist) if all(visited) else -1)

Submission status: Accepted

Solution code:

from collections import deque

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

graph = [[] for _ in range(N * N)]
inserted = [0] * (N * N)
for i, nodes in enumerate(X):
    for j1, j2 in zip(nodes[:-1], nodes[1:]):
        n1 = max(i, j1 - 1) * N + min(i, j1 - 1)
        n2 = max(i, j2 - 1) * N + min(i, j2 - 1)
        graph[n1].append(n2)
        inserted[n2] += 1

dist = [0] * (N * N)
visited = [False] * (N * N)
for i in range(N):
    visited[i * N + i] = True

q = deque()
for i, v in enumerate(inserted):
    if v == 0:
        q.append(i)
        visited[i] = True
        dist[i] = 1

while q:
    u = q.popleft()
    for v in graph[u]:
        if visited[v]:
            continue

        inserted[v] -= 1
        if inserted[v] == 0:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

print(max(dist) if all(visited) else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    match = [collections.deque(nb()) for _ in range(n)]

    nxt = [-1] * n
    waiting = collections.deque(range(n))
    cnt = [0] * n

    while len(waiting) > 0:
        ego = waiting.popleft()
        if len(match[ego]) == 0:
            continue

        enemy = match[ego].popleft()

        if nxt[enemy] == ego:
            waiting.append(ego)
            waiting.append(enemy)
            cnt[ego] = cnt[enemy] = max(cnt[ego], cnt[enemy]) + 1

        else:
            nxt[ego] = enemy

    if any(match):
        print(-1)
    else:
        print(max(cnt))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [LIST() for _ in range(N)]

match = defaultdict(int)
cnt = 0
for i, j in combinations(range(N), 2):
	match[(i, j)] = cnt
	match[(j, i)] = cnt
	cnt += 1

V = N*(N-1)//2
graph = [[] for _ in range(V)]
dag = [0]*V
for i in range(N):
	for j in range(N-2):
		graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
		dag[match[(i, A[i][j+1]-1)]] += 1

q = deque([i for i in range(V) if dag[i]==0])
day = [1]*V
ans = 1

while q:
	p = q.popleft()
	for v in graph[p]:
		dag[v] -= 1
		if dag[v] == 0:
			day[v] = day[p]+1
			ans = day[v]
			q.append(v)


if any(dag):
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def main():
	N = INT()
	A = [LIST() for _ in range(N)]

	match = defaultdict(int)
	cnt = 0
	for i, j in combinations(range(N), 2):
		match[(i, j)] = cnt
		match[(j, i)] = cnt
		cnt += 1

	V = N*(N-1)//2
	graph = [[] for _ in range(V)]
	dag = [0]*V

	for i in range(N):
		for j in range(N-2):
			graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
			dag[match[(i, A[i][j+1]-1)]] += 1

	q = deque([i for i in range(V) if dag[i] == 0])
	day = [1]*V
	while q:
		p = q.popleft()
		for v in graph[p]:
			dag[v] -= 1
			if dag[v] == 0:
				day[v] = day[p]+1
				q.append(v)
				ans = day[v]

	if any(dag):
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [LIST() for _ in range(N)]

match = defaultdict(int)
cnt = 0
for i, j in combinations(range(N), 2):
	match[(i, j)] = cnt
	match[(j, i)] = cnt
	cnt += 1

V = N*(N-1)//2
graph = [[] for _ in range(V)]
dag = [0]*V

for i in range(N):
	for j in range(N-2):
		graph[match[(i, A[i][j]-1)]].append(match[(i, A[i][j+1]-1)])
		dag[match[(i, A[i][j+1]-1)]] += 1

q = deque([i for i in range(V) if dag[i] == 0])
day = [1]*V
while q:
	p = q.popleft()
	for v in graph[p]:
		dag[v] -= 1
		if dag[v] == 0:
			day[v] = day[p]+1
			q.append(v)
			
if any(dag):
	print(-1)
else:
	print(max(day))

Submission status: Accepted

Solution code:
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
wait=[[float("inf")]*N for _ in range(N)]
for i in range(N):
  wait[A[i][0]-1][i]=0
L=[list(range(N)),[]]
finish=[0]*N

day=0
ind=0
while L[ind]:
  battle=False
  day+=1
  for player in L[ind]:
    if finish[player]>=N-1:
      continue
    enemy=A[player][finish[player]]-1
    if wait[player][enemy]<day and wait[enemy][player]<day:
      battle=True
      #print("day{},{}vs{}".format(day,player+1,enemy+1))
      finish[player]+=1
      finish[enemy]+=1
      if finish[player]<N-1:
        wait[A[player][finish[player]]-1][player]=day
      if finish[enemy]<N-1:
        wait[A[enemy][finish[enemy]]-1][enemy]=day
      L[(ind+1)%2].append(player)
      L[(ind+1)%2].append(enemy)
  L[ind]=[]   
  ind=(ind+1)%2
  if not battle:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    depths = [0] * V  # depths[i] := the length of the longest path to V_i
    order = [i for i in range(first_index, V) if not in_degrees[i]]
    queue = deque(order)

    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = cur_depth + 1
                queue.append(v), order.append(v)

    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    # https://atcoder.jp/contests/abc139/tasks/abc139_e
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        source = -1
        for j in a:
            target = ids[i][j]
            if source != -1:
                graph[source].append(target)
                in_degrees[target] += 1
            source = target

    _, depths = cycle_detectable_topological_sort(graph, in_degrees)
    print(max(depths) + 1 if depths else -1)


def grl_4_a():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
    V, _, *ST = map(int, open(0).read().split())
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print(1 if res is None else 0)


if __name__ == "__main__":
    abc139_e()
    # grl_4_a()

Submission status: Accepted

Solution code:
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = cur_depth + 1
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def abc139_e():
    # https://atcoder.jp/contests/abc139/tasks/abc139_e
    N, *A = map(int, open(0).read().split())

    ids = [[-1] * (N + 1) for _ in range(N + 1)]
    cur_id = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            ids[i][j] = ids[j][i] = cur_id
            cur_id += 1

    graph = [[] for _ in range(N * (N - 1) // 2)]
    in_degrees = [0] * (N * (N - 1) // 2)
    for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
        source = -1
        for j in a:
            target = ids[i][j]
            if source != -1:
                graph[source].append(target)
                in_degrees[target] += 1
            source = target

    _, depths = cycle_detectable_topological_sort(graph, in_degrees)
    print(max(depths) + 1 if depths else -1)


def grl_4_a():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
    V, _, *ST = map(int, open(0).read().split())
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print(1 if res is None else 0)


if __name__ == "__main__":
    abc139_e()
    # grl_4_a()