Graph Valid Tree

Q: Какова временная сложность задачи Graph Valid Tree?

O(n + m) с поиском в глубину, где m — количество рёбер, и O(n + m α(n)) с системой непересекающихся множеств. Оба метода сначала проверяют количество рёбер, поэтому граф с неправильным количеством отклоняется до начала поиска.

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

+10

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

Верните true, если рёбра образуют одно дерево из всех n узлов: из каждого узла можно попасть в любой другой, и циклов нет. В противном случае верните false.

Функция

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: количество узлов, пронумерованных от 0 до n-1
edgesinteger-2d-array: неориентированные рёбра, каждое из которых представляет собой пару [a, b]
Возвращаетboolean: true, если рёбра соединяют все n узлов в одно дерево, иначе false

Ограничения

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] при этом 0 ≤ a, b ≤ n-1 и a ≠ b
Ни одно ребро не встречается дважды ни в одном направлении.

Примеры

Ввод: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Вывод: true
Пояснение: Узел 0 соединён с узлами 1, 2 и 3, а узел 4 ответвляется от узла 1. Четыре ребра соединяют все пять узлов без циклов, поэтому это дерево.

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

Ввод: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Вывод: false
Пояснение: Есть 3 ребра, то есть n-1, но они образуют цикл 0, 1, 2, 0, а у узла 3 вообще нет ребра.

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

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

Подсказки

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

Открыто 0 из 3

Решение

Дерево связно и не содержит циклов. При ровно n-1 рёбрах эти условия эквивалентны: такой граф связен тогда и только тогда, когда в нём нет циклов. Поэтому сначала проверьте количество рёбер, а затем либо один раз проверьте связность, либо позвольте структуре union-find обнаружить ребро, соединяющее две уже связанные вершины.

Ищите путь перед каждым ребром

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

Идея

Добавляйте рёбра по одному. Перед добавлением [u, v] выполните поиск от u по уже добавленным рёбрам. Если до v можно добраться, новое ребро становится вторым путём между ними и замыкает цикл, как [1, 3] во втором примере. Если ни одно ребро не замыкает цикл, граф является лесом, а последний поиск от узла 0 показывает, является ли он одним деревом.

При каждой проверке выполняется поиск по всему графу, построенному к этому моменту. Для пути из 5001 узла, рёбра которого поступают по порядку, поиски посещают 1 + 2 + ... + 5000 узлов — около 12,5 миллиона.

Алгоритм

Начни с пустого списка смежности для каждой вершины.
Для каждого ребра [u, v] выполни поиск из u по рёбрам, добавленным на данный момент. Если он достигает v, верни false.
В противном случае добавь ребро в списки обеих вершин.
В конце верни результат проверки, достигает ли поиск из вершины 0 всех n вершин.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Сосчитай рёбра, затем выполни поиск один раз

Идея

Начни с n отдельных узлов и добавляй рёбра по одному. Каждое ребро либо соединяет две группы, оставляя на одну группу меньше, либо попадает внутрь группы и замыкает цикл. Чтобы получить одну группу, нужно n-1 соединений. Поэтому при числе рёбер меньше n-1 граф не может быть связным, а большее число рёбер обязательно замкнёт цикл: второй пример, 5 рёбер на 5 узлах, не проходит уже по одному только количеству.

При ровно n-1 рёбрах граф в итоге состоит из одной группы только в том случае, если каждое ребро было соединением, то есть ни одно ребро не замкнуло цикл. Поэтому, когда количество верное, проверь только связность: один поиск из узла 0 должен достичь всех n узлов. В третьем примере он достигает только 0, 1 и 2. При m = n-1 списки и поиск требуют O(n).

Алгоритм

Если edges.length не равно n-1, верните false.
Создайте список смежности, сохраняя каждое ребро у обоих его концов.
Поместите узел 0 в стек и отметьте его как посещённый.
Извлекайте узлы из стека и помещайте в него каждого ещё не посещённого соседа, отмечая его и увеличивая счётчик при добавлении.
Верните результат проверки, равно ли количество n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Подсчёт рёбер и структура непересекающихся множеств

Идея

Структура «система непересекающихся множеств» определяет, образует ли каждое ребро цикл, без поиска. Каждая вершина изначально образует отдельную группу. Для ребра [u, v] найдите корень для каждой из его вершин. Корни разные: ребро соединяет две части, поэтому объедините их. Корень один и тот же: u и v уже связаны, и ребро замыкает цикл. Если все n-1 рёбер приводят к объединению, то в итоге n групп образуют одну: дерево.

Два правила помогают поддерживать короткие цепочки родителей. При объединении корень меньшей группы становится потомком корня большей, поэтому при 10^4 вершинах ни одна цепочка не превышает 13 шагов. Во время поиска указывайте для каждой пройденной вершины её предка через одного. Вместе эти правила обеспечивают сложность m операций O(m α(n)), где α — обратная функция Аккермана, которая здесь не превышает 4. Сложность по памяти — O(n).

Алгоритм

Если edges.length не равно n-1, верни false.
Установи parent[x] = x и размер группы 1 для каждого узла.
Для каждого ребра [u, v] переходи от u и v по родителям к их корням, указывая для каждого пройденного узла его дедушку.
Корни совпадают: верни false.
Корни разные: присоедини корень меньшей группы к другой группе и прибавь ее размер.
Если каждое ребро объединило две группы, верни true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    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)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

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

Проверка только на наличие цикла. Три отдельных ребра на шести узлах не образуют цикла, но при этом получаются три компоненты.
Проверка только количества рёбер. В третьем примере n-1 ребро, но цикл 0, 1, 2 занимает узел 3, необходимый для ребра.
Хранение каждого ребра только у одного конца. [1, 0] тоже соединяет узлы 0 и 1, а поиск из узла 0 не находит узел 1.
Проверка цикла с помощью поиска в глубину, которая не пропускает родительский узел. Каждое ребро ведёт прямо обратно к узлу, откуда вы пришли, поэтому условие «встретили посещённого соседа» срабатывает в любом дереве.
Рекурсивный обход длинного пути. В цепочке из 5001 узла глубина вызовов достигает 5000, что превышает ограничение Python по умолчанию — 1000; используйте явный стек.

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

Какова временная сложность задачи Graph Valid Tree?

O(n + m) с поиском в глубину, где m — количество рёбер, и O(n + m α(n)) с системой непересекающихся множеств. Оба метода сначала проверяют количество рёбер, поэтому граф с неправильным количеством отклоняется до начала поиска.

Почему у дерева с n узлами n-1 ребро?

Постройте дерево, начиная с одного узла, и добавляйте остальные по одному. Каждый новый узел присоединяется ровно одним ребром: без ребра он был бы отрезан, а с двумя замкнул бы цикл. Поэтому для n узлов требуется n-1 рёбер.

Как обнаружить цикл в неориентированном графе?

В структуре «система непересекающихся множеств» ребро, концы которого уже имеют общий корень, замыкает цикл. При поиске в глубину цикл — это посещённый сосед, отличный от узла, из которого вы пришли, поэтому нужно отслеживать родителя каждого узла. Для системы непересекающихся множеств не нужны ни родитель, ни список смежности.

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

Тест #1

Тест #2

Тест #3

Аргументы

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

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

true

Graph Valid Tree

Функция

Ограничения

Примеры

Подсказки

Решение

Ищите путь перед каждым ребром

Сосчитай рёбра, затем выполни поиск один раз

Подсчёт рёбер и структура непересекающихся множеств

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

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

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