Привет! Меня зовут Евгений, и сегодня я представляю курс «Алгоритмы и структуры данных» Яндекс Практикума. В этой статье хочу вам рассказать про задачу, которая долгое время была проблемой для многих наших студентов. В том числе расскажу про несколько вариантов решения и о том, как их можно доработать.
Также я расскажу про решение с помощью теории графов, основная алгоритмическая сложность которого заключается в чтении входных данных.
«Железные дороги»: условие задачи
Начну с условия.
В стране X есть n городов, которым присвоены номера от 1 до n. Столица страны имеет номер n. Между каждой парой городов проложена железная дорога.
Однако дороги могут быть двух типов по ширине полотна. Любой поезд может ездить только по одному типу полотна. Условно, один тип дорог помечают как R, а другой как B. То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет проехать по этому маршруту. От одного города до другого можно проехать только по маршруту, состоящему исключительно из дорог типа R или только из дорог типа B.
Но это ещё не всё.
По дорогам страны X можно двигаться только от города с меньшим номером к городу с бо́льшим номером. Это объясняет большой приток жителей в столицу, у которой номер n.
Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B. Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бо́льшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя.
Выясните, является ли данная вам карта оптимальной.
Перед тем как читать дальше, попробуйте решить задачу самостоятельно. Возможно, у вас появится своё уникальное решение.
Divide et impera
Когда я попал на курс, я прорешал задачи курса без заглядывания в теорию. И вот как я решал эту задачу.
Можно попробовать в лоб проверить, что для каждой вершины s множество достижимых по красным рёбрам не совпадает с множеством достижимых по синим. Такой подход требует запуска DFS для каждой вершины два раза. DFS работает за O(E), а для каждой вершины за O(V * E). Это решение явно очень медленное, но его можно доработать.
Для начала можно попробовать подумать, что из себя представляют неоптимальные пути. Поскольку в графе есть пути между каждой парой вершин, можно сразу сказать, что длина одного из них 1.
Лемма 1 |
Тут всё очевидно. Получается, если две вершины соединяют неоптимальные маршруты, в качестве одного из них можно рассматривать ребро между вершинами.
Будем путь из одного ребра называть основным маршрутом, а другого цвета — альтернативным (альтернативный маршрут — это путь между вершинами с рёбрами одного цвета, отличающегося от цвета ребра, которое соединяет эти вершины).
Что можно сказать насчёт альтернативных?
Лемма 2 |
Таким образом можно рассмотреть все тройки вершин (s < v < d) и проверить, что они не образуют неоптимальные маршруты. То есть путь s→v→d одного цвета, а ребро s→d другого.
Это решение всё ещё имеет сложность O(V^3) и не проходит по времени. Но его реализация явно проще. Вот его имплементация на Python.
def get_color(edges, s, d):
assert(s < d)
return edges[s][d - s - 1]
def check_vertices(n, edges):
for s in range(n - 2):
for v in range(s + 1, n - 1):
for d in range(v + 1, n):
if get_color(edges, s, v) == get_color(edges, v, d) and \
get_color(edges, s, v) != get_color(edges, s, d):
return False;
return True
def read_matrix(n):
matrix = [[False] * n for _ in range(n)]
for i in range(n - 1):
for j, type_road in enumerate(input().rstrip(), start=i + 1):
if type_road == 'R':
matrix[i][j] = True
else:
matrix[j][i] = True
def main():
n = int(input())
edges = [input() for _ in range(n - 1)]
print("YES" if check_vertices(n, edges) else "NO")
if __name__ == "__main__":
main()
Можно ли уменьшить количество троек? Конечно. Не надо рассматривать тройки, если рёбра s→v и s→d имеют одинаковый цвет. То есть все вершины, выходящие из s, можно разбить на два множества: в первое входят вершины, в которые входят красные рёбра из s, а во второе — вершины, в которые входят синие рёбра.
Теперь в качестве кандидатов d и v можно рассматривать только вершины из разных множеств.
def check_vertices(n, edges):
for s in range(n - 2):
red_vertices = []
blue_vertices = []
for v in range(s + 1, n):
if get_color(edges, s, v) == 'R':
red_vertices.append(v)
else:
blue_vertices.append(v)
for red in red_vertices:
for blue in blue_vertices:
if red < blue:
if get_color(edges, red, blue) == "R":
return False
else:
if get_color(edges, blue, red) == "B":
return False
return True
Такое решение в разы быстрее, но всё равно имеет сложность O(V^3). А что можно сказать про рёбра между этими множествами, если нет вершины, в которую из s ведут два неоптимальных маршрута?
Тогда из первого множества (в которые входят красные рёбра) во второе ведут только синие рёбра. А из второго в первое только красные. Значит, две вершины не могут лежать в разных множествах, и при этом путь не может заходить в другое множество.
Поэтому эти множества можно рассматривать дальше независимо.
def check_vertices(n, edges):
stack = [list(range(n))]
while stack:
vertices = stack.pop()
blue_vertices = []
red_vertices = []
start = vertices[0]
for vertex in vertices[1:]:
if get_color(edges, start, vertex) == "B":
blue_vertices.append(vertex)
else:
red_vertices.append(vertex)
for red in red_vertices:
for blue in blue_vertices:
if red < blue:
if get_color(edges, red, blue) == "R":
return False
else:
if get_color(edges, blue, red) == "B":
return False
for new_vertices in (blue_vertices, red_vertices):
if len(new_vertices) > 1:
stack.append(new_vertices)
return True
Здесь каждое ребро определяет либо к какому множеству принадлежит конец, либо проверяет цвет пограничных. И поэтому рассматривается только один раз.
Сложность такого алгоритма O(E). Для меня полученное решение казалось очевидным. Но за три года от студентов я его так ни разу не увидел.
Решение через поиск циклов
А на что рассчитывал автор задачи? В курсе рассказывается, как с помощью DFS можно проверить ориентированный граф на наличие цикла.
Тут нет циклов как таковых, но два пути между вершинами на них похожи. Достаточно развернуть рёбра одного цвета — тогда на основе неоптимального графа получается цикл.
И теперь достаточно проверить, что в новом графе G' нет циклов. Это можно сделать за O(E).
def check_vertex(matrix, colors, start):
stack = [start]
while stack:
vertex = stack.pop()
if colors[vertex] == 0:
colors[vertex] = 1
stack.append(vertex)
for neighbour in matrix[vertex]:
if colors[neighbour] == 1:
return False
if colors[neighbour] == 0:
stack.append(neighbour)
elif colors[vertex] == 1:
colors[vertex] = 2
return True
def is_acyclic(matrix):
n = len(matrix)
colors = [0] * n
for i in range(n):
if colors[i] == 0 and not check_vertex(matrix, colors, i):
return False
return True
def main():
n = int(input().rstrip())
matrix = [[] for _ in range(n)]
for i in range(n-1):
for j, type_road in enumerate(input().rstrip(), start=i+1):
if type_road == "R":
matrix[i].append(j)
else:
matrix[j].append(i)
print("YES" if is_acyclic(matrix) else "NO")
if __name__ == "__main__":
main()
Возникает вопрос: почему мы можем так сделать?
Рассмотрим граф с циклом.
Лемма 3 |
Вторая идея уже тоже знакома. Достаточно рассмотреть только тройки.
Лемма 4 |
Таким образом, если в графе есть цикл, то есть цикл длины 3. А из наличия последнего следует неоптимальность исходного графа.
Что ещё можно улучшить?
Можно ли улучшить это решение? В данном случае да.
Если есть вершина с входящей степенью 0, достаточно запустить DFS только из неё. Очевидно, таких вершин может быть не больше одной.
А что, если такой вершины нет? Значит, можно доказать, что в графе точно есть цикл.
Лемма 5 |
def is_acyclic(matrix):
n = len(matrix)
out_degree = [0] * n
for outs in matrix:
for vertex in outs:
out_degree[vertex] += 1
candidates = [vertex for vertex, degree in enumerate(out_degree) if degree == 0]
return len(candidates) == 1 and check_vertex(matrix, [0] * n, candidates[0])
Ещё можно сразу сказать, что эта вершина в цикле не участвует, и рассмотреть граф без неё. При этом входящая степень остальных вершин уменьшится на 1.
И так после нескольких повторений мы либо получим граф без такой вершины, либо топологически его отсортируем. Это приводит нас к ещё одной лемме.
Лемма 6 |
И получается довольно простое решение, которое можно записать в несколько строк:
n = int(input().rstrip())
adjacency = [0] * n
for i in range(n - 1):
for j, type_road in enumerate(input().rstrip(), start=i + 1):
adjacency[i if type_road == "R" else j] += 1
print("YES" if len(set(adjacency)) == n else "NO")Очевидно, что по времени сложность такого решения O(E), а по памяти — O(V) (не считая системных издержек).
Это уже давно есть в математике
Ориентированные графы, у которых между каждой парой вершин есть ребро, имеют специальное название — «турниры».
А леммы 2 и 5 — это часть большой теоремы:
Теорема. Следующие утверждения для графа-турнира с
'n'вершинами эквивалентны:— граф ацикличен;
— граф не содержит циклов длины 3;
— последовательность входящих степеней графа есть{0,1,2,…, n−1}.
После вопроса о корректности решения студенты пару раз вспоминали эту теорему, но полностью ей не пользовались.
Надеюсь, вам понравилась статья, и ход моих рассуждений был понятен. Если остались вопросы, давайте обсудим их в комментариях.
