Уязвимые переправы: мосты и острова-узлы

Если ты помнишь критерий моста low[to] > tin[v], точки сочленения с >= и почему пропускают ребро, а не вершину, листай до «Теперь сам».

Как думаешь, какой мост важнее

Двенадцать островов, пятнадцать мостов. Противник может разрушить один мост за ход. Какой мост ему рушить, чтобы отрезать часть твоих островов? Как это найти, не перебирая все варианты?

Ответь себе до чтения. Мост отрезает часть архипелага, только если других путей между его концами нет - то есть мост не лежит ни на одном цикле. Мост внутри треугольника из островов разрушать бесполезно: обойдут по двум другим сторонам. Перебор «разрушить и проверить» честен, но обходит карту столько раз, сколько мостов. Обход в глубину отвечает на вопрос «лежит ли ребро на цикле» для всех рёбер разом.

На что это похоже

Эвакуация из района. Чтобы понять, какие переезды критичны, не нужно по очереди перекрывать каждый и смотреть на пробки. Достаточно для каждого квартала спросить: «есть ли у тебя выезд, который обходит этот переезд?» Если весь район за переездом может выбраться только через него - переезд критичен. Величина low - это ответ квартала: насколько «назад» он может выбраться в обход.

Механизм: tin, low и два критерия

Обход в глубину нумерует острова временем входа tin. Величина low[v] - самое раннее время входа, до которого можно дотянуться из поддерева v, пройдя вниз по дереву обхода и затем не более одного раза по ребру назад, к уже открытому острову. Мост v - to, по которому обход спустился в to, - критический, если low[to] > tin[v]: из поддерева to нет хода назад ни до v, ни выше, и единственная связь - этот мост.

Остров v - узел (точка сочленения), если у него есть ребёнок to с low[to] >= tin[v]: из поддерева to нельзя выбраться выше v, минуя сам v. Нестрогое неравенство - потому что дотянуться до самого v мало: без v этот путь тоже пропадает. Корень обхода - особый случай: он узел, только если у него в дереве обхода не меньше двух детей.

Обе величины считаются за один проход, O(V + E). Важная деталь: при обходе пропускают мост, по которому пришли, а не остров, из которого пришли. Пока между двумя островами один мост, разницы нет. Когда мостов два, второй мост - законный путь назад, и пропускать его нельзя.

Правило

Критические мосты и острова-узлы ищут одним обходом в глубину: мост критичен при low[to] > tin[v], остров - узел при low[to] >= tin[v], корень - при двух детях. Пропускай ребро, по которому пришёл, а не вершину: иначе параллельные мосты станут ложно критическими.

Разбор: три критических моста из пятнадцати

Архипелаг из четырёх треугольников островов, соединённых цепочкой. Мост хранится номером: по номеру его и пропускают.

# 12 островов, 15 мостов [a, b]; номер моста - его место в списке
mosty = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3],
         [4, 6], [6, 7], [7, 8], [8, 6], [8, 9], [9, 10], [10, 11],
         [11, 9]]
N = 12
rabota = [0]

def sosedi_bez(zapret):
    # списки смежности без моста номер zapret: [сосед, номер моста]
    s = []
    for v in range(N):
        s.append([])
    for i in range(len(mosty)):
        if i != zapret:
            s[mosty[i][0]].append([mosty[i][1], i])
            s[mosty[i][1]].append([mosty[i][0], i])
    return s

def svyazno(s):
    # обход в ширину от острова 0: достижимы ли все?
    byl = [False] * N
    byl[0] = True
    och = [0]
    golova = 0
    while golova < len(och):
        v = och[golova]
        golova = golova + 1
        for p in s[v]:
            rabota[0] = rabota[0] + 1
            if not byl[p[0]]:
                byl[p[0]] = True
                och.append(p[0])
    return len(och) == N

# наивно: убрать каждый мост по очереди и обойти архипелаг
naivno = []
for i in range(len(mosty)):
    if not svyazno(sosedi_bez(i)):
        naivno.append(i)
r1 = rabota[0]

# один обход в глубину: tin - время входа, low - самое раннее время,
# до которого дотягивается поддерево одним обратным ребром (раздел 10)
s = sosedi_bez(-1)
tin = [-1] * N
low = [0] * N
vremya = [0]
kriticheskie = []

def dfs(v, prishli_po):
    tin[v] = vremya[0]
    low[v] = vremya[0]
    vremya[0] = vremya[0] + 1
    for p in s[v]:
        rabota[0] = rabota[0] + 1
        if p[1] == prishli_po:       # тот же МОСТ, а не та же вершина
            continue
        if tin[p[0]] == -1:
            dfs(p[0], p[1])
            low[v] = min(low[v], low[p[0]])
            if low[p[0]] > tin[v]:
                kriticheskie.append(p[1])
        else:
            low[v] = min(low[v], tin[p[0]])

rabota[0] = 0
# карта связна; иначе обход запускают из каждой непосещённой вершины
dfs(0, -1)
kriticheskie.sort()
print("наивно:  ", naivno, "|", r1, "проверок соседей")
print("один DFS:", kriticheskie, "|", rabota[0], "проверок соседей")
for i in kriticheskie:
    print("   мост", i, ":", mosty[i][0], "-", mosty[i][1])

наивно:   [3, 7, 11] | 378 проверок соседей
один DFS: [3, 7, 11] | 30 проверок соседей
   мост 3 : 2 - 3
   мост 7 : 4 - 6
   мост 11 : 8 - 9

Оба способа нашли мосты 2-3, 4-6 и 8-9 - те, что соединяют треугольники. Мосты внутри треугольников не критичны: каждый лежит на цикле. Наивный способ обошёл карту 15 раз: двенадцать обходов связной карты по 28 проверок соседей и три обхода разрезанной - по 6, 14 и 22, смотря какой кусок отрезан, - всего 378; один обход в глубину посмотрел каждый мост с двух концов - 30. На карте в 16 384 клетки с десятками тысяч переходов разница уже в тысячи раз: E · (V + E) против V + E.

Разбор: двойной мост и острова-узлы

Остров 0 соединён с портом 1 двумя мостами. Разрушить один - ничего не изменится. Обход ниже написан без рекурсии, со стеком: на настоящей карте глубина обхода доходит до тысяч, а рекурсия в Python ограничена (обычно около тысячи вызовов, у учебного движка - двести).

# остров 0 и порт 1 связаны ДВУМЯ мостами - разрушить нужно оба
mosty = [[0, 1], [0, 1], [1, 2], [2, 3], [3, 4], [4, 2], [4, 5]]
N = 6
s = []
for v in range(N):
    s.append([])
for i in range(len(mosty)):
    s[mosty[i][0]].append([mosty[i][1], i])
    s[mosty[i][1]].append([mosty[i][0], i])

def najti(po_mostu):
    # po_mostu=True - пропускаем мост, по которому пришли;
    # False - пропускаем вершину, из которой пришли (ошибка)
    tin = [-1] * N
    low = [0] * N
    vremya = [0]
    mosty_krit = []
    uzly = set()
    stek = [[0, -1, -1, 0]]           # [вершина, мост, откуда, детей]
    # обход в глубину без рекурсии: на стеке позиция в списке соседей
    poziciya = [0] * N
    tin[0] = 0
    low[0] = 0
    vremya[0] = 1
    while len(stek) > 0:
        verh = stek[len(stek) - 1]
        v = verh[0]
        if poziciya[v] < len(s[v]):
            p = s[v][poziciya[v]]
            poziciya[v] = poziciya[v] + 1
            if po_mostu and p[1] == verh[1]:
                continue
            if not po_mostu and p[0] == verh[2]:
                continue
            if tin[p[0]] == -1:
                tin[p[0]] = vremya[0]
                low[p[0]] = vremya[0]
                vremya[0] = vremya[0] + 1
                verh[3] = verh[3] + 1
                stek.append([p[0], p[1], v, 0])
            else:
                low[v] = min(low[v], tin[p[0]])
        else:
            stek.pop()
            if len(stek) > 0:
                otec = stek[len(stek) - 1][0]
                low[otec] = min(low[otec], low[v])
                if low[v] > tin[otec]:
                    mosty_krit.append(verh[1])
                if otec != 0 and low[v] >= tin[otec]:
                    uzly.add(otec)
            elif verh[3] >= 2:
                uzly.add(v)          # корень - узел, если детей двое
    return [sorted(mosty_krit), sorted(uzly)]

print("пропуск по мосту:  ", najti(True), "- [мосты, острова-узлы]")
print("пропуск по вершине:", najti(False))

пропуск по мосту:   [[2, 6], [1, 2, 4]] - [мосты, острова-узлы]
пропуск по вершине: [[0, 2, 6], [1, 2, 4]]

Правильная версия нашла два критических моста - 1-2 и 4-5 - и три острова-узла: порт 1 (без него остров 0 отрезан), остров 2 (без него порт отрезан от треугольника) и остров 4 (без него отрезан остров 5). Версия «пропускать вершину» добавила мост 0 - один из двух параллельных. Пришла в порт по первому мосту, второй мост ведёт в ту же вершину и был пропущен, - и low порта не узнал об обходном пути. Граница правила: узлы и мосты - про разрушение ОДНОГО элемента. Если противник рушит два моста за ход, вопрос другой - сколько мостов надо разрушить, чтобы разрезать архипелаг, - и это минимальный разрез из раздела 12.

Что ломается без этого

Подсказка «стратегический мост» на двойной переправе. Игрок тратит ход на разрушение моста, а враг спокойно идёт по второму.

Генератор без контроля прочности. Карта связна, но держится на одном мосту - первая же атака режет архипелаг пополам, и партия решается на втором ходу.

Рекурсивный обход на большой карте. На тестовой карте 32 × 32 всё работает, на настоящей сервер падает с переполнением стека вызовов.

Зачем это в работе

Мосты и точки сочленения - это единые точки отказа: единственный канал между дата-центрами, единственный маршрутизатор между сегментами сети, единственная дорога в посёлок, единственный сотрудник, через которого идёт согласование. Один обход находит их все, и это первый отчёт, который строят по любой схеме связей.

Теперь сам

1. Острова 0-1-2-3 по кругу (0-1, 1-2, 2-3, 3-0) и остров 4, соединённый мостом с 2. Какие мосты критичны, какие острова - узлы?
2. Почему корень обхода проверяют отдельно, а не тем же low[to] >= tin[v]?
3. Между двумя островами три параллельных моста. Сколько из них критичны?