Список компараторов в сортировочных сетях

Question

У меня есть вопрос в моем домашнем задании, и мне трудно вовремя визуализировать и понять вопрос. Вопрос в следующем:

Мы можем представить сеть сравнения с n-входами с c компараторами в виде списка из c пар целых чисел в диапазоне от 1 до n. Если две пары содержат общее целое число, порядок соответствующих компараторов в сети определяется порядком пар в списке. Учитывая это представление, опишите O(n + c)-временный (последовательный) алгоритм для определения глубины сети сравнения.

Что значит иметь пары целых чисел в контексте сетей сравнения? Обычно мы использовали обозначения ниже для обозначения сети сравнения, где каждая горизонтальная линия представляет число.

Answer 1

Это означает, что если у вас есть пара (1, 2), это одна из тех вертикальных линий, а именно та, которая соединяет горизонтальные линии 1 и 2.

Таким образом, верхняя левая часть этой картинки будет представлена ​​как (1, 2) (3, 4) (1, 3) (2, 4).

Глубина только этой части равна 2.

Answer 2

for i = 1, n 
  depth[i] = 0

total_depth = 0
for j = 1, c
  i1 = comparators[j].entry1
  i2 = comparators[j].entry2
  new_depth = 1 + max(depth[i1], depth[i2])
  depth[i1] = new_depth
  depth[i2] = new_depth
  total_depth = max(total_depth, new_depth)

print(total_depth)