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:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    A[i] = [i-1 for i in map(int, input().split())]


def pair(x,y):
    if x<y:
        return (x,y)
    else:
        return (y,x)

to_index = dict()
to_pair = dict()
idx = 0
for i in range(N):
    for j in range(i+1,N):
        to_index[(i,j)] = idx
        to_pair[idx] = (i,j)
        idx += 1
    
MAX_N = idx
# DAG TopoSort
in_count = [0]*MAX_N
edge = [[] for _ in range(MAX_N)]

for i in range(N):
    for j in range(N-2):
        vnum = to_index[pair(i,A[i][j+1])]
        pvnum = to_index[pair(i, A[i][j])]
        edge[pvnum].append(vnum)

for i in range(MAX_N):
    for v in edge[i]:
        in_count[v] += 1

S = []
L = [] #Sort結果
index = [0]*MAX_N # 頂点vのLにおけるインデックスindex[v]
ans = 0

for i in range(MAX_N):
    if in_count[i]==0: S.append(i)

while S:
    ans += 1
    new = []
    for _ in range(len(S)):
        v = S.pop()
        index[v] = len(L)
        L.append(v)
        for nv in edge[v]:
            in_count[nv] -= 1
            if in_count[nv]==0:
                new.append(nv)
    S = []
    for n in new:
        S.append(n)


if len(L) != MAX_N:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
def opp(i):  #対戦希望相手
    return a[i][nex[i]]

from sys import stdin
#入力
readline=stdin.readline
n=int(readline())
m=n*(n-1)//2
a=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

nex=[0]*n
before=set(range(n))
day=0
for day in range(1,m+1):
    now=set()
    while len(before)>0:
        p=before.pop()
        q=opp(p)
        if opp(q)==p and p not in now and q not in now:
            nex[p]+=1
            nex[q]+=1
            if nex[p]<n-1:
                now.add(p)
            if nex[q]<n-1:
                now.add(q)
            if q in before:
                before.remove(q)
    before=now
    if len(before)==0:
        break

if min(nex)==n-1:
    print(day)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = []
for _ in range(n):
    tmp = inpl()
    tmp = [x-1 for x in tmp] + [-1]
    # print(tmp)
    a.append(deque(tmp))
md = [0] * n
nx = [-1] * n
for i in range(n):
    nx[i] = a[i].popleft()
q = deque(range(n))

while q:
    x = q.popleft()
    y = nx[x]
    if nx[y] == x:
        d = max(md[x], md[y])
        md[x] = md[y] = d+1
        nx[x] = a[x].popleft()
        nx[y] = a[y].popleft()
        q.append(x); q.append(y)
if any(x for x in a):
    print(-1)
else:
    print(max(md))

Submission status: Accepted

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

n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(1, n ** 2):
    qq = set()
    for x in q:
        if a[a[x][0]][0] == x:
            qq.add(x)
            qq.add(a[x][0])
    if qq:
        q = []
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break

Submission status: Accepted

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

n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
cnt = 0
while q:
    cnt += 1
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0]][0] == x:
            qq.add(x)
            qq.add(a[x][0])
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        exit()
print(cnt)

Submission status: Accepted

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

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
q = list(range(n))
for cnt in range(1, n ** 2 + 2):
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0] - 1][0] == x + 1:
            qq.add(x)
            qq.add(a[x][0] - 1)
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        break
    if not q:
        print(cnt)
        break

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = [None] * n
    for i in range(n):
        tmp = list(map(lambda x:int(x) - 1, input().split()))
        tmp.reverse()
        A[i] = tmp

    now = set()
    for i in range(n):
        j = A[i][-1]
        if i == A[j][-1]:
            now.add((min(i, j), max(i, j)))

    cnt = 0
    while now:
        next = set()
        for i, j in now:
            A[i].pop()
            A[j].pop()

        for i0, i1 in now:
            for i in (i0, i1):
                if not A[i]:
                    continue
                j = A[i][-1]
                if not A[j]:
                    continue
                if i == A[j][-1]:
                    next.add((min(i, j), max(i, j)))

        now = next
        cnt += 1

    if any(row for row in A):
        print(-1)
        return
    print(cnt)
resolve()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]

graph = [[] for _ in range(n * n)]


def calc(i, j):
    if j > i:
        i, j = j, i
    return i * n + j


to = [0] * (n * n)
for i in range(n):
    for j in range(n - 2):
        u = calc(i, AA[i][j] - 1)
        v = calc(i, AA[i][j + 1] - 1)
        graph[u].append(v)
        to[v] += 1
start = []
for i in range(n * n):
    if to[i] == 0:
        start.append(i)


def topological_sort(edge_num, graph, start, to):
    topo = []
    cnt = 0
    stack = deque(start)
    while stack:
        v = stack.popleft()
        topo.append(v)
        cnt += 1
        for u in graph[v]:
            to[u] -= 1
            if to[u] == 0:
                stack.append(u)
    return topo, cnt


topo, cnt = topological_sort(n * n, graph, start, to)
if cnt != n * n:
    print(-1)
    exit()
day = [1] * (n * n)
for i in topo:
    for j in graph[i]:
        day[j] = day[i] + 1
print(max(day))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]

D = [0] * N
Nx = [-1] * N
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i].popleft()
    Nx[i] = j

    if Nx[j] == i:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i].popleft()
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]

D = [0] * N
canBattle = defaultdict(lambda: False)
que = deque(range(N))

while que:
    i = que.popleft()
    j = A[i][0]
    canBattle[(i, j)] = True

    if canBattle[(j, i)]:
        A[i].popleft()
        A[j].popleft()
        day = max(D[i], D[j])
        D[i] = D[j] = day + 1

        if A[i]:
            que.append(i)
        if A[j]:
            que.append(j)

if all(len(a) == 0 for a in A):
    print(max(D))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
from time import time
S = time()

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1.700:
        print(N * (N - 1) // 2)
        exit()
    if not isChanged:
        break

print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
serial = [[0]*N for _ in range(N)]
c = 0

for i in range(N):
    for j in range(i+1, N):
        serial[i][j] = c
        serial[j][i] = c
        c += 1

ins = [0]*c
outs = defaultdict(list)

for i in range(N):
    for j in range(N-2):
        s = serial[i][A[i][j]-1]
        t = serial[i][A[i][j+1]-1]
        ins[t] += 1
        outs[s].append(t)

q = deque([v for v in range(c) if ins[v]==0])
ans = 0

while True:
    nq = deque([])
    
    while q:
        v = q.popleft()
    
        for nv in outs[v]:
            ins[nv] -= 1
        
            if ins[nv]==0:
                nq.append(nv)

    ans += 1
    
    if len(nq)==0:
        break
    
    q = nq

if ins==[0]*c:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
calc=lambda u,v:min(u,v)*n+max(u,v)
edge=[[]for _ in range(n*n)]
for i in range(n):
  for j in range(1,n-1):
    u,v=calc(a[i][j-1]-1,i),calc(a[i][j]-1,i)
    edge[u].append(v)
from collections import deque
def find_loop(n,e):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  return t
d=find_loop(n*n,edge)
if len(d)!=n*n:exit(print(-1))
c=[1]*n*n
for i in d:
  for j in edge[i]:
    c[j]=c[i]+1
print(max(c))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [LI() for _ in range(N)]
    p = [0] * N
    cnt = 0
    c = [0] * N
    while cnt < N*(N-1)//2:
        ud = False
        for i in range(N):

            while p[i] < N-1:
                j = dq[i][p[i]]-1
                if dq[j][p[j]]-1 == i:
                    c[i] = c[j] = max(c[i],c[j]) + 1
                    p[i] += 1; p[j] += 1
                    cnt += 1
                    ud = True
                else:
                    break
        if ud:
            continue
        else:
            print(-1)
            return
    print(max(c))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
start = time.time()

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(i, 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)
elapsed_time = time.time() - start
# print(elapsed_time)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
"""
愚直に考えると、
・今XXX日目です
・試合できる人は試合をします。
・その日一回でも試合があれば次の日に進んで、なかったらおわり
をやる。愚直にやろうとすると、
・各選手について、次に試合する相手
・各選手がその日に試合したかどうか（１日に同じ人が複数回試合できないので）
・現在XXX日目
などの情報を持つ必要があり、また、その日の終わりに、各選手が試合したかどうかなどから、その日１回でも試合があったか判定をしたり、処理がめんどくさい。

ちょっとひねった方法で考えると、
・各選手が順番に、自分が次に試合するべき相手を一人指名して場にカードを出す。
・マッチングが成立する（a->b, b->a のカードが両方場に出される）と、その試合が実施され、試合した二人の選手について、次に試合したい選手がいれば、またカードを場に出す
・aとbが試合した時の最短の日にちは、max(aが最後に試合した日, bが最後に試合した日)+1 で表される
・各選手がカードを出したにも関わらず、マッチングが成立しない場合は、与えられた順番で試合ができない。

の形で管理すると、今日は何日で～とか、その日一回でも試合があったか～とかを管理しなくてよい。
"""

from collections import deque

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


q = deque()
for i in range(N):
    q.append(i)

next_game_with = [-1] * N
end_by = [0] * N
while q:
    a = q.popleft()
    opponent = A[a].popleft() - 1
    if next_game_with[opponent] == a:
        end_by[a] = end_by[opponent] = max(end_by[a], end_by[opponent]) + 1
        if A[a]:
            q.append(a)
        if A[opponent]:
            q.append(opponent)
    else:
        next_game_with[a] = opponent

finished = True
for i in range(N):
    if A[i]:
        finished = False
        break
if finished:
    print(max(end_by))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(n-1):
        a[i][j] -= 1

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2

to = [[] for _ in range(MAXV)]
# 頂点番号
id = [[0 for _ in range(MAXN)] for _ in range(MAXN)]
def toID(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]

# 頂点番号のラベリング
V = 0
for i in range(n):
    for j in range(n):
        if i < j:
            id[i][j] += V
            V += 1

# aを、頂点番号に書き換え、試合の依存関係を表す辺を張る(辺の向きは逆にする)
for i in range(n):
    for j in range(n-1):
        a[i][j] = toID(i, a[i][j])
    for j in range(n-2):
        to[a[i][j+1]].append(a[i][j])

# dfsする
visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)] # loop 検出用
dp = [0 for _ in range(MAXV)] # max length of path from v
def dfs(v):
    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)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

ans = 0
ok = True
for i in range(V):
    res = dfs(i)
    if res == -1:
        ok = False
        break
    ans = max(ans, res)
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
edges = [[] for _ in range(n * 1001)]
memo = []
start = set()
for i in range(n):
    A = list(map(int, input().split()))
    for j in range(n-1):
        if i < A[j] - 1:
            A[j] = i * 1000 + A[j] - 1
        else:
            A[j] = (A[j] - 1) * 1000 + i

    for j in range(n-2):
        edges[A[j]].append(A[j+1])
    memo.append(A[0])

memo = Counter(memo).most_common()
for x, t in memo:
    if t > 1:
        start.add(x)

#閉路検出/最長のパス
d = [-1 for _ in range(1001 * n)]
def dfs(v):
    d[v] = -2
    l = 0
    for to in edges[v]:
        if d[to] == -2:
            print(-1)
            exit()
        if d[to] == -1:
            dfs(to)
        l = max(l, d[to] + 1)
    d[v] = l

if len(start) == 0:
    print(-1)
    exit()
for i in start:
    dfs(i)
print(max(d) + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
g = [[]*(n*(n-1)//2) for _ in range(n*(n-1)//2)]
chk = set([])
cnt = 0
d = {}
st = set([])

for i in range(n):
  a = [int(i) for i in readline().split()]
  for j in range(n-2):
    A,b = min(a[j],i+1),max(a[j],i+1)
    p,q = min(a[j+1],i+1),max(a[j+1],i+1)    
    if not b*1000+A in chk:
      d[b*1000+A] = cnt
      cnt += 1
      chk.add(b*1000+A)
    if not q*1000+p in chk:
      d[q*1000+p] = cnt
      cnt += 1
      chk.add(q*1000+p)
    g[d[b*1000+A]].append(d[q*1000+p])
    if j == 0:
      st.add(d[b*1000+A])

# あとは頂点VのグラフをdfsしてLongest pathの長さを求める
# -1: unchecked, -2: checked and uncalculated
dp=[-1]*(n*(n-1)//2)
#flag=True
def dfs(v):
    #global flag
    dp[v]=-2
    length=0
    for nv in g[v]:
        if(dp[nv]==-2):
            print(-1)
            exit()
        if(dp[nv]==-1):
            dfs(nv)
        length=max(length,dp[nv]+1)
    dp[v]=length
            
st = list(st)
a = []
pp = 0
for i in st:dfs(i)
print(max(dp)+1)

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    INF = float('inf')

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

    adjL = [[] for _ in range(N*N)]
    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        x, y = i, As[0]
        if x > y:
            x, y = y, x
        vPrev = x*N + y
        for A in As[1:]:
            x, y = i, A
            if x > y:
                x, y = y, x
            v = x*N + y
            adjL[vPrev].append(v)
            indegs[v] += 1
            vPrev = v

    def getMaxCostsDAG(adjList, indegs, INF):
        numV = len(adjList)
        vs = [v for v in range(numV) if indegs[v] == 0]
        costs = [INF] * numV
        for v in vs:
            costs[v] = 0
        Q = deque(vs)
        while Q:
            vNow = Q.popleft()
            cost = costs[vNow]
            for v2 in adjList[vNow]:
                indegs[v2] -= 1
                if indegs[v2] == 0:
                    costs[v2] = cost + 1
                    Q.append(v2)
        return costs

    costs = getMaxCostsDAG(adjL, indegs, INF)

    ans = max(costs)
    if ans == INF:
        print(-1)
    else:
        print(ans+1)


solve()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

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

    for i in range(n):
        if len(a[i]) != 0:
            print(-1)
            return
    print(day)
    
resolve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

    day = 0
    numMatch = 0
    ps = set(range(N))
    isReadys = [0] * N
    iAs = [-1] * N
    while True:
        day += 1
        p2s = set()
        for p in ps:
            iAs[p] += 1
            if iAs[p] == N-1: continue
            q = Ass[p][iAs[p]]
            if isReadys[q] and Ass[q][iAs[q]] == p:
                isReadys[q] = 0
                p2s.add(p)
                p2s.add(q)
                numMatch += 1
            else:
                isReadys[p] = 1
        if numMatch >= N*(N-1)//2:
            print(day)
            break
        if not p2s:
            print(-1)
            break
        ps = p2s

solve()

Submission status: Accepted

Solution code:


from collections import deque


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


next_vs = [None] * N
day_finished = [0] * N
q = deque()
for i in range(N):
    q.append(i)

"""
・試合したらそいつらをキューに積む
・試合できなかったら、次はこいつと戦いたいよリストにいれる

キューを全て確認したのに、　次はこいつと戦いたいよリストが残っている/未試合の相手が残っている　状態であれば、与えられた順では試合ができない
"""

while q:
    x = q.popleft()
    opp_x = A[x].popleft()

    if next_vs[opp_x] == x:
        day_finished[x] = day_finished[opp_x] = max(day_finished[x], day_finished[opp_x]) + 1
        if A[x]:
            q.append(x)
        if A[opp_x]:
            q.append(opp_x)

    else:
        next_vs[x] = opp_x

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


print(max(day_finished))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def edge_to_vertex(n, i, j):
        'convert edge(i,j) (1-index) to vertex'
        return (2 * n - i) * (i - 1) // 2 + (j - i - 1)
    
    def topological_bfs(m, adj):
        sorted_vertices = []
        dim = [0] * m
        for i in range(m):
            for j in adj[i]:
                dim[j] += 1
        q = deque()
        for i in range(m):
            if dim[i] == 0:
                q.append(i)
        while q:
            u = q.popleft()
            assert(dim[u] == 0)
            sorted_vertices.append(u)
            for v in adj[u]:
                dim[v] -= 1
                if dim[v] == 0:
                    q.append(v)
        return sorted_vertices


    
    n = ii()
    # 試合の組み合わせを頂点へと変換し有向グラフ隣接リストへと変換する前処理 O(n^2)
    m = n * (n - 1) // 2
    adj = [[] for _ in range(m)]
    for i in range(1, n + 1):
        L = lmi()
        vertices = [edge_to_vertex(n, min(i, j), max(i, j)) for j in L]
        for k in range(1, n - 1):
            u, v = vertices[k-1], vertices[k]
            adj[u].append(v)
    # print(adj)

    # BFS トポロジカルソートを用いて閉路判定 O(n^2)
    topological_sorted = topological_bfs(m, adj)
    if len(topological_sorted) != m:
        print(-1)
    # 入次数 0 の頂点からトポロジカルソート順に辺を緩和し、最大距離を返す O(n^2)
    else:
        cost = [1] * m
        for u in topological_sorted:
            for v in adj[u]:
                cost[v] = max(cost[u], cost[u] + 1)
        print(max(cost))
 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""

ある試合(a,b)が行われるまでに消化しておくべき試合を管理して、それが0になった組からキューに積む
みたいな感じで雑にやるとTLEが取れなかった。


LeetCodeのTwoSum的に、
a -> bで試合ができない場合は、情報を残しておいて、b -> a が回ってきた時に試合が実施されるようにするとよいっぽい
"""
from collections import deque

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


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    # 互いの初めに戦うべき相手がお互いであれば、そのペアで試合を行う
    if next_opponent[b] == a:
        # a,bが今までに試合した回数の多いほう+1（同じ人が日に二度試合を行えないので）
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で一番初めに戦う相手がaではないなら、順番が来るまで待つ
    # このあと(b,c)の試合が行われて、キューにb,cが積まれるとかで、aがbと試合するとかがあれば、消化される
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))

Submission status: Accepted

Solution code:
import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_set=set()
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if i in matched_set:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not ai_next in matched_set:
      #print(i,ai_next,answer)
      matched_set.add(amat[i].pop())
      matched_set.add(amat[ai_next].pop())
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    sys.exit()
  elif cleared_num==N:
    print(answer)
    sys.exit()