Redundant Connection

СреднеСистема непересекающихся множеств Графы

+10

Сеть изначально была деревом: n узлов, пронумерованных от 1 до n, соединённых n-1 неориентированными рёбрами без циклов. Затем добавили ещё одно ребро между двумя узлами, которые не были соединены напрямую, поэтому теперь список edges содержит n рёбер и ровно один цикл.

Верните ребро, которое можно удалить, чтобы остальные n-1 рёбер снова образовали дерево. Если подходят несколько рёбер, верните то, которое встречается последним в edges, в виде пары [a, b] — точно так, как она там записана.

Функция

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: n неориентированных рёбер, каждое из которых представляет собой пару [a, b] узлов, пронумерованных от 1
Возвращаетinteger-array: ребро цикла, которое последним появляется в edges, записанное так, как оно там указано

Ограничения

3 ≤ n ≤ 5000, где n = edges.length
edges[i] = [a, b], где 1 ≤ a, b ≤ n и a ≠ b
Ни одно ребро не встречается дважды ни в одном из направлений.
Рёбра соединяют все n узлов и образуют ровно один цикл.

Примеры

Ввод: edges = [[1, 2], [1, 3], [2, 3]]
Вывод: [2, 3]
Пояснение: Три ребра образуют треугольник 1, 2, 3, поэтому удаление любого из них оставляет дерево. [2, 3] стоит последним в списке.

Ввод: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Вывод: [1, 4]
Пояснение: Цикл: 1, 2, 3, 4, 1. Ребро [1, 5] не входит в него: если его удалить, узел 5 окажется отрезанным. Из четырёх рёбер цикла последним встречается [1, 4].

Дополнительный вопрос

Если бы рёбра были направленными, а исходный граф представлял собой корневое дерево, какое ребро вы бы удалили, если из-за дополнительного ребра у узла оказалось два родителя?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Удаление ребра оставляет дерево ровно в том случае, если это ребро лежит на единственном цикле графа, поэтому ответ — ребро цикла, которое последним встречается в списке. Структура непересекающихся множеств находит его за один проход: добавляй рёбра по порядку, и первое ребро, концы которого уже соединены, и есть ответ.

Попробуйте удалять каждое ребро, начиная с последнего

Верно, но не успевает на самых больших тестах

Идея

Удалите одно ребро и проверьте, образуют ли остальные n-1 рёбер дерево. При n вершинах и n-1 рёбрах они образуют дерево тогда и только тогда, когда один обход, начатый из вершины 1, достигает всех n вершин. Проверяйте рёбра с конца списка, чтобы первым прошло удаление самого позднего ребра. Сохраните индекс каждого ребра в списках смежности — тогда при обходе можно пропустить удалённое ребро, ничего не перестраивая.

Каждая проверка — это полный обход за O(n), а проверок может быть n: до 2.5 × 10^7 шагов при n = 5000.

Алгоритм

Создайте списки смежности, в которых для каждого соседа хранится индекс ведущего к нему ребра.
Для skip, перебирая индексы от последнего до 0, выполните поиск, начиная с узла 1, и игнорируйте ребро с индексом skip.
Подсчитайте узлы, достигнутые при поиске.
Если поиск достигает всех n узлов, верните edges[skip].

def findRedundantConnection(edges):
    n = len(edges)
    # graph[x] holds (neighbour, index of the edge) for every edge at node x.
    graph = [[] for _ in range(n + 1)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))
    # Try leaving out each edge, the last one first.
    for skip in range(n - 1, -1, -1):
        # Without edge skip, can node 1 still reach all n nodes?
        seen = [False] * (n + 1)
        seen[1] = True
        stack = [1]
        reached = 1
        while stack:
            node = stack.pop()
            for nxt, i in graph[node]:
                if i != skip and not seen[nxt]:
                    seen[nxt] = True
                    reached += 1
                    stack.append(nxt)
        # n-1 edges that connect n nodes form a tree.
        if reached == n:
            return edges[skip]
    return []

Снимите листья

Идея

Лист, узел с одним ребром, не может находиться на цикле, потому что цикл входит в каждый свой узел и выходит из него. Удаление листа может превратить его соседа в лист, поэтому продолжай удалять листья, пока они не закончатся. Останется ровно цикл, поскольку у каждого узла цикла сохраняются два ребра цикла. Во втором примере удаляется узел 5, у узла 1 остаются два ребра, а узлы с 1 по 4 остаются.

Любое ребро между двумя оставшимися узлами — это ребро цикла, потому что вторая связь между узлами цикла создала бы второй цикл. Поэтому просканируй edges с конца и верни первое ребро, оба конца которого остались.

Алгоритм

Постройте списки смежности и подсчитайте степень каждого узла.
Поместите в стек каждый узел степени 1.
Извлеките лист, установите его степень равной 0 и уменьшите степень его оставшегося соседа; поместите этого соседа в стек, когда его степень станет равна 1.
Когда стек опустеет, узлы со степенью больше 0 образуют цикл.
Просматривайте edges с конца и верните первое ребро, оба конца которого остались.

def findRedundantConnection(edges):
    n = len(edges)
    graph = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    # A node with one edge cannot lie on the cycle. Remove it, and repeat.
    stack = [x for x in range(1, n + 1) if degree[x] == 1]
    while stack:
        leaf = stack.pop()
        degree[leaf] = 0
        for nxt in graph[leaf]:
            if degree[nxt] > 0:
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    stack.append(nxt)
    # Only the cycle is left. Its edge that comes last in the list is the answer.
    for u, v in reversed(edges):
        if degree[u] > 0 and degree[v] > 0:
            return [u, v]
    return []

Система непересекающихся множеств: первое ребро, замыкающее цикл

Идея

Добавляй рёбра в порядке списка и отслеживай, какие узлы связаны. Пока цикл не замкнулся, каждое ребро соединяет две части, между которыми нет пути. Первое ребро, концы которого уже связаны, замыкает цикл. Остальные рёбра цикла были добавлены раньше, поэтому именно это ребро цикла появляется последним. Во втором примере [1, 4] обнаруживает, что узлы 1 и 4 уже соединены, а [1, 5] никогда не считывается.

Структура «система непересекающихся множеств» хранит один массив, parent; переход по указателям от узла приводит к корню его части. Присоединение меньшей части к большей и перенаправление указателей узлов на их «дедушек» во время find позволяет сохранять цепочки короткими. Тогда амортизированная стоимость каждой операции равна O(α(n)), где α — обратная функция Аккермана — не превышает 4 для любых реальных входных данных.

Алгоритм

Направьте каждый узел от 1 до n на самого себя, parent[x] = x, и задайте ему размер 1.
Просмотрите edges по порядку. Для [u, v] найдите корень u и корень v.
Если корни совпадают, [u, v] замыкает цикл: верните его в исходном виде.
Если нет, большая часть поглощает меньшую: её корень становится родителем корня меньшей части, а размеры складываются.

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # every node starts as its own group
    size = [1] * (n + 1)

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # u and v are already connected: this edge closes the cycle.
        if a == b:
            return [u, v]
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return []

Ловушки и крайние случаи

Возврат последнего ребра списка. Во втором примере это [1, 5], и его удаление отсекает узел 5.
Сканирование с начала после удаления листьев. Это возвращает самое раннее ребро цикла — [1, 2] во втором примере.
Сортировка или перестановка пары. Если в списке находится [3, 1], верните [3, 1], а не [1, 3].
Выделение массивов для узлов от 0 до n-1. Нумерация узлов начинается с 1, поэтому для узла n нужен массив из n+1 ячеек.
Рекурсивный обход цикла. Он может пройти через все 5000 узлов — это в пять раз больше стандартного лимита рекурсии Python, поэтому используйте явный стек и цикл в find.

Частые вопросы3

Какова временная сложность задачи «Избыточное соединение»?

Структура объединения-поиска решает эту задачу за один проход по n рёбрам: время O(n · α(n)), где α(n) на практике не превышает 4, и память O(n). Удаление листьев тоже выполняется за O(n). Попытка выполнить каждое удаление с новым поиском обходится в O(n²).

Какие рёбра можно удалить, чтобы осталась древесная структура?

Именно рёбра цикла. Для каждого из них существует второй путь между его концами по остальной части цикла, поэтому его удаление сохраняет связность графа. Любое другое ребро — единственная связь между двумя частями графа, и его удаление разделяет их.

Можно ли решить задачу «Избыточное соединение» с помощью DFS?

Да. Перед добавлением каждого ребра выполните поиск от одного его конца по уже добавленным рёбрам; первое ребро, другой конец которого уже достижим, и будет ответом. Это требует O(n) на ребро и O(n²) в целом, тогда как структура непересекающихся множеств отвечает на тот же вопрос почти за константное время.

def findRedundantConnection(edges):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

edges = [[1, 2], [1, 3], [2, 3]]

Ожидаемый вывод

[2, 3]

Redundant Connection

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте удалять каждое ребро, начиная с последнего

Снимите листья

Система непересекающихся множеств: первое ребро, замыкающее цикл

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи