Как найти минимальное количество дней для расписания в соответствии с предпочтениями с помощью графика? ⇐ Python

[Anonymous]

Мне поставлен вопрос следующего содержания:
У нас есть n игроков и мы хотим провести турнир по борьбе ровно из n * (n - 1)/2 матчей. В каждый день игрок может сыграть не более одного матча. Однако у каждого игрока есть определенные предпочтения, когда дело доходит до игры с другими. Вот пример ввода:

Код: Выделить всё

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

В этом примере игрок 1 хочет сыграть против 4 2 3 по порядку. Это означает, что они хотят сыграть против игрока 4, прежде чем играть против игрока 2 и так далее. Я должен найти решение на основе графика, которое выведет наименьшее количество дней, необходимое для планирования такого турнира, или выведет -1, если это невозможно.
Мое решение состояло в том, чтобы создать очередь предпочтений для каждого игрока. Затем для каждого дня постройте граф предпочтений, в котором ребро (u, v) существует тогда и только тогда, когда v находится в начале очереди предпочтений ребра u. Затем я использую DFS для извлечения всех циклов длиной 2. Эти циклы представляют двух игроков, которые готовы играть друг с другом, и я добавляю пару в связанный список под названием «матч». Затем я удаляю очередь предпочтений указанной пары и продолжаю делать это до тех пор, пока либо все не будут играть против игроков, против которых они хотят играть, либо мы не достигнем невозможного решения, при котором ни один из двух игроков не хочет играть друг против друга, в этом случае такой график невозможен. Наихудший случай выполнения этого алгоритма — Θ(n^3), а лучший — Θ(n^2), что, к сожалению, приводит к ограничениям по времени при отправке, поэтому либо сам алгоритм не лучший, либо его можно реализовать лучше.
Вот решение на Python:

Код: Выделить всё

from typing import Optional
from collections import deque

class SinglyListNode:
def __init__(self, key):
self.key = key
self.next: Optional["SinglyListNode"] = None

class SinglyLinkedList:

def __init__(self):
self.head: Optional[SinglyListNode] = None

def listPrepend(self, key):
node = SinglyListNode(key)
node.next = self.head
self.head = node

def listDelete(self, node: SinglyListNode):
if node == self.head:
self.head = node.next
else:
prev = self.head
while prev is not None and prev.next != node:
prev = prev.next
prev.next = node.next

def listSearch(self, key):
x = self.head
while x is not None and x.key != key:
x = x.next
return x

class Vertex:

def __init__(self, number: int):
self.number = number
self.color = None
self.parent = None
self.d = None
self.f = None

class DirectedGraph:

def __init__(self, n: int):
self.V = [Vertex(i) for i in range(n)]
self.E_n = 0
self.Adj = [SinglyLinkedList() for _ in range(n)]
# match is a linked list which stores cycles of length 2
self.match = SinglyLinkedList()
self.time = 0

def addEdge(self, u: Vertex, v: Vertex):
self.Adj[u.number].listPrepend(v)
self.E_n += 1

def removeEdge(self, u: Vertex, v: Vertex):
node = self.Adj[u.number].listSearch(v)
self.Adj[u.number].listDelete(node)
self.E_n -= 1

def isEmpty(self) -> bool:
return self.E_n == 0

def DFS(self):
for u in self.V:
u.color = 'W'
u.parent = None
self.time = 0
self.match.head = None
for u in self.V:
if u.color == 'W':
self.DFS_VISIT(u)

def DFS_VISIT(self, u: Vertex):
self.time += 1
u.d = self.time
u.color = 'G'
x = self.Adj[u.number].head
while x is not None:
v = x.key
if v.color == 'W':
v.parent = u
self.DFS_VISIT(v)
elif v.color == 'G':
# A cycle is now detected.  Check if it is of length 2
# meaning that two players want to play against each other
# If yes, add the pair (v, u) to `match`.
cycle_len = u.d - v.d + 1
if cycle_len == 2:
self.match.listPrepend((v, u))
x = x.next
self.time += 1
u.f = self.time
u.color = 'B'

def wrestlingTournament(n: int, pref):
G = DirectedGraph(n)
# `P_Q` is an array of queue's storing each player's preferences
P_Q = [deque() for i in range(n)]
for (i, i_pref) in enumerate(pref):
for j in i_pref:
P_Q[i].append(G.V[j])
for i in range(n):
if len(P_Q[i]) > 0:
G.addEdge(G.V[i], P_Q[i][0])
G.DFS()
# the loop ends only when all matches are covered (the graph is empty)
# or when there is no viable schedule
days = 0
while not G.isEmpty() and G.match.head != None:
days += 1
x = G.match.head
# `match` is a linked list which stores pairs of vertices
# that create a cycle of length 2
while x is not None:
(u, v) = x.key
P_Q[u.number].popleft()
G.removeEdge(u, v)
P_Q[v.number].popleft()
G.removeEdge(v, u)
if len(P_Q[u.number]) > 0:
G.addEdge(u, P_Q[u.number][0])
if len(P_Q[v.number]) > 0:
G.addEdge(v, P_Q[v.number][0])
x = x.next
G.DFS()
if G.isEmpty():
return days
else:
return -1

if __name__ == "__main__":
n = int(input())
pref = [
[int(x) - 1 for x in input().split()]
for _ in range(n)
]
print(wrestlingTournament(n, pref))

Наша техническая оценка говорит, что существует решение, которое всегда работает в Θ(n^2), и что мы должны использовать топологическую сортировку. Однако я не понимаю, как топологическая сортировка может нам здесь помочь. Если мы используем топологическую сортировку на каждом из графов предпочтений, то это, по сути, то же самое, что и DFS. Если мы используем его на полном графе, где каждая вершина соединена с каждой другой вершиной, я не понимаю, чем это нам поможет.
Вопрос дает нам значение n в первой строке. Тогда в следующих n строках у нас будет n — 1 число, обозначающее предпочтения каждого игрока. Например, приведенный в начале пример интерпретируется как:

Код: Выделить всё

n = 4
1: 4 > 2 > 3
2: 3 > 4 > 1
3: 2 > 4 > 1
4: 1 > 2 > 3

Я стремлюсь к решению на основе графов. Реализация на самом деле не требуется, достаточно подробного псевдокода.

Подробнее здесь: https://stackoverflow.com/questions/798 ... erence-via