Is Graph Bipartite

+10

Граф содержит n узлов с метками от 0 до n-1. Каждая пара [a, b] в edges — это неориентированное ребро между узлом a и узлом b. Граф может состоять из нескольких отдельных частей, а некоторые узлы могут вообще не иметь рёбер.

Граф является двудольным, если его узлы можно разделить на две группы так, чтобы каждое ребро соединяло узел из одной группы с узлом из другой. Верните true, если граф двудольный, и false в противном случае.

Функция

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

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

Ограничения

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

Примеры

Ввод: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Вывод: true
Пояснение: Поместите узлы 0 и 2 в одну группу, а узлы 1 и 3 — в другую. Каждое из четырёх рёбер соединяет две группы.

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

Выбор группы для одного узла определяет группу для остальной связанной с ним части: сосед переходит в другую группу. Раскрасьте каждую часть с помощью поиска в ширину, чередуя два цвета; граф является двудольным тогда и только тогда, когда ни одно ребро не соединяет вершины одного цвета. Граф может быть несвязным, поэтому каждый нераскрашенный узел начинает новый поиск.

Попробуй все варианты разбиения

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

Идея

Попробуй все разбиения. Считай группу каждого узла одним битом: тогда n битов образуют двоичное число, и перебор от 0 до 2^n-1 охватывает каждое разбиение ровно один раз. Для каждого разбиения проверь каждое ребро и верни true, если найдётся разбиение, при котором каждое ребро пересекает границу между группами. Число разбиений удваивается с каждым узлом: для 20 узлов получается около миллиона.

Алгоритм

Для каждого числа от 0 до 2^n-1 поместите узел i в группу, заданную битом i.
Если каждое ребро соединяет две группы, верните true.
Если ни одно разбиение не подходит, верните false.

def isBipartite(n, edges):
    side = [0] * n  # side[x] is 0 or 1: the group of node x in the current split
    while True:
        # Does every edge cross between the two groups?
        if all(side[u] != side[v] for u, v in edges):
            return True
        # Move to the next split, counting in binary over side.
        i = 0
        while i < n and side[i] == 1:
            side[i] = 0
            i += 1
        if i == n:
            return False  # all 2^n splits have been tried
        side[i] = 1

Объединение и поиск среди соседей каждой вершины

Идея

В какую бы группу ни попал узел, все его соседи попадают в другую, поэтому они делят группу. Для каждого узла объедини всех его соседей в одно множество структуры «система непересекающихся множеств»; тогда множество содержит узлы, которые должны находиться на одной стороне. Ребро, оба конца которого находятся в одном множестве, вынуждено оставаться внутри одной группы, поэтому граф не является двудольным.

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

Алгоритм

Установите parent[x] = x и anchor[x] = -1 для каждого узла.
Для каждого ребра [u, v] укажите каждый конец в качестве якоря другого, если у него ещё нет якоря.
Объедините v с множеством anchor[u], а u — с множеством anchor[v].
Верните false, если оба конца какого-либо ребра находятся в одном множестве; в противном случае верните true.

def isBipartite(n, edges):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n
    anchor = [-1] * n  # the first neighbour seen for each node

    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

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # All neighbours of a node must sit on one side: the side opposite the node.
    for u, v in edges:
        if anchor[u] == -1:
            anchor[u] = v
        if anchor[v] == -1:
            anchor[v] = u
        union(anchor[u], v)  # v joins the other neighbours of u
        union(anchor[v], u)  # u joins the other neighbours of v
    # An edge whose two ends were forced onto one side cannot cross.
    for u, v in edges:
        if find(u) == find(v):
            return False
    return True

Раскраска в два цвета каждого компонента в ширину

Идея

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

Поиск рассматривает только свою компоненту, поэтому пройдись по всем узлам и начинай новый поиск от каждого ещё не раскрашенного узла. В третьем примере поиск от узла 0 раскрашивает узлы 0 и 1. Поиск от узла 2 присваивает узлу 2 цвет 0, а узлам 3 и 4 — цвет 1, а затем находит [3, 4], у которых на обоих концах цвет 1: false. Каждый узел раскрашивается и добавляется в очередь один раз, и каждая из 2m записей в списках сравнивается один раз: время и память O(n + m).

Алгоритм

Создай списки смежности, добавив каждое ребро к обоим его концам, и установи для всех цветов значение -1.
Для каждой неокрашенной вершины по порядку назначь ей цвет 0 и добавь её в очередь.
Извлеки вершину из очереди. Назначь каждому неокрашенному соседу противоположный цвет и добавь его в очередь; если у соседа тот же цвет, верни false.
Когда все части будут окрашены, верни true.

from collections import deque


def isBipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = [-1] * n  # -1: not colored yet, otherwise 0 or 1
    for start in range(n):
        if color[start] != -1:
            continue
        # A new component: its first node can take either color.
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == -1:
                    # A neighbour must take the other color.
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # this edge stays inside one group
    return True

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

Поиск только из узла 0. Третий пример работает для узла 0 и даёт сбой среди узлов 2, 3 и 4.
Добавление каждого ребра только в один список. Для рёбер [1, 0] и [2, 0] узел 0 получает цвет 0 и не видит соседей; затем узел 1 тоже получает цвет 0, и его ребро к узлу 0 выглядит как конфликт, хотя разбиение на части работает.
Раскрашивание узла при извлечении из очереди. Тогда узел может попасть в очередь дважды, и при втором посещении первый цвет будет перезаписан. Раскрашивай узел при добавлении в очередь.
Путаница между двудольностью и отсутствием циклов. В квадрате есть цикл, но он двудольный; разбиение нарушают только циклы нечётной длины.

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

Какова временная сложность задачи «Двудольный граф»?

Раскраска поиском в ширину или в глубину выполняется за O(n + m) для m рёбер: каждый узел окрашивается один раз, а каждое ребро сравнивается один раз с каждого конца. Списки смежности и цвета занимают O(n + m) памяти. Структура непересекающихся множеств даёт тот же ответ за O(n + m α(n)).

Почему нечётный цикл делает граф не двудольным?

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

Следует ли использовать BFS или DFS, чтобы проверить, является ли граф двудольным?

Подойдут оба варианта: правило раскраски одинаковое, меняется только порядок обхода. Для больших графов записывай DFS с явным стеком, поскольку рекурсивная версия может углубляться на один вызов для каждой вершины.

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

true

Is Graph Bipartite

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй все варианты разбиения

Объединение и поиск среди соседей каждой вершины

Раскраска в два цвета каждого компонента в ширину

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

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

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