Как указывалось, эта проблема не всегда имеет решение. Поскольку каждая вершина должна иметь хотя бы одно входящее ребро, если у нас E
Итак, давайте предположим, что у нас E> = V. Вот один из подходов к алгоритму: во-первых, посчитайте количество ребер, прикрепленных к каждой вершине за O (E) время. Обратите внимание, мое решение предполагает соответствующее хранилище, такое как список смежности. Вы понимаете, почему матрица смежности будет иметь более сложную структуру?
Во-вторых, мы создадим двоичный minheap вершин, в соответствии с их соответствующим числом ребер, в O (V). Немного интуиции: если у нас есть вершина только с одним ребром, мы должны преобразовать ее во входящий ребро! Когда мы назначаем направление этого ребра, нам нужно обновить число ребер вершины на другой стороне. Если эта другая вершина идет от 2 ребер к 1, мы теперь вынуждены назначить направление ее одного ребра влево. Визуально:
1 - 2 - 1
Произвольно выберите 1 ребро, чтобы сделать направленным
1 - 2 -> 0
2 только что потерял преимущество, поэтому обновите до 1!
1 - 1 -> 0
Поскольку теперь у него только 1 ребро, преобразуйте его во входящее!
0 -> 0 -> 0
Очевидно, этот график не работает, так как V> E, но вы поняли.
Итак, V раз мы извлекаем минимум из кучи и фиксируем в O (logV). Каждый раз уменьшайте число ребер соседа. Предполагая список смежности, мы можем найти соседа (первый элемент) и обновить счет в O (1), и мы можем снова исправить кучу в O (logV). В целом, этот шаг занимает O (V logV).
Обратите внимание: если все наши оставшиеся вершины имеют более одного возможного ребра, этот подход произвольно выберет одну из вершин с наименьшим числом ребер и произвольно выберет одно из его ребер. Я дам вам подумать о том, почему это работает (или попытаюсь привести контрпример, если вы считаете, что это не так!) Наконец, если E> V, то когда мы закончим, могут остаться лишние ненужные ребра. За время O (E) мы можем произвольно назначить направления этим ребрам.
В целом, мы смотрим на V + V * logV + E aka O (E + VlogV). Надеюсь, это поможет!