Is Graph Bipartite

+10

Un grafo tiene n nodos, etiquetados del 0 al n-1. Cada par [a, b] en edges es una arista no dirigida entre el nodo a y el nodo b. El grafo puede dividirse en varias partes separadas, y algunos nodos pueden no tener ninguna arista.

Un grafo es bipartito cuando puedes dividir sus nodos en dos grupos, de modo que cada arista conecte un nodo de un grupo con un nodo del otro. Devuelve true si el grafo es bipartito y false en caso contrario.

Función

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

ninteger: el número de nodos, numerados del 0 al n-1
edgesinteger-2d-array: las aristas no dirigidas, cada una un par [a, b]
Devuelveboolean: verdadero si los nodos se pueden dividir en dos grupos con todas las aristas entre los grupos; falso en caso contrario

Restricciones

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] con 0 ≤ a, b ≤ n-1 y a ≠ b
No aparece ninguna arista dos veces, en ninguna dirección.

Ejemplos

Entrada: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Salida: true
Explicación: Pon los nodos 0 y 2 en un grupo y los nodos 1 y 3 en el otro. Cada una de las cuatro aristas conecta los dos grupos.

Entrada: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Salida: false
Explicación: La arista [0, 1] se divide correctamente y el nodo 5 no tiene aristas, pero los nodos 2, 3 y 4 forman un triángulo. Basta con que una parte falle para que la respuesta sea false.

Para ir más allá

Cuando el grafo no es bipartito, ¿puedes devolver un ciclo de longitud impar como prueba, indicando sus nodos en orden?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Elegir un grupo para un nodo obliga a que el resto de su componente conexa vaya al otro grupo: un vecino pasa al otro grupo. Colorea cada componente con una búsqueda en anchura que alterne dos colores; el grafo es bipartito exactamente cuando ninguna arista tiene el mismo color en ambos extremos. El grafo puede estar desconectado, así que cada nodo sin colorear inicia una nueva búsqueda.

Prueba todas las divisiones

Correcto, pero no termina con las pruebas más grandes

Intuición

Prueba cada partición. Trata el grupo de cada nodo como un bit, de modo que los n bits formen un número binario, y contar de 0 a 2^n-1 visita cada partición una vez. Para cada partición, comprueba cada arista y devuelve true si alguna partición hace que todas las aristas la atraviesen. El número de particiones se duplica con cada nodo: 20 nodos dan aproximadamente un millón.

Algoritmo

Para cada número de 0 a 2^n-1, coloca el nodo i en el grupo indicado por el bit i.
Si cada arista une los dos grupos, devuelve true.
Si ninguna división funciona, devuelve 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

Union-find en los vecinos de cada nodo

Intuición

En cualquier grupo en el que quede un nodo, todos sus vecinos quedan en el otro, así que comparten un grupo. Para cada nodo, une a todos sus vecinos en un conjunto de union-find; después, un conjunto contiene los nodos obligados a estar en el mismo lado. Una arista cuyos dos extremos están en un mismo conjunto debe permanecer dentro de un grupo, así que el grafo no es bipartito.

La comprobación detecta todos los casos de fallo. En torno a un ciclo impar, unir dos aristas a la vez conecta su primer nodo con el último, y la arista de cierre conecta esos dos. Sin un ciclo impar, cada unión conecta dos nodos que están a una distancia par, por lo que se encuentran en el mismo lado. El primer vecino de un nodo, su ancla, identifica el conjunto de sus vecinos, así que puedes unirlos a medida que pasan las aristas, sin listas de adyacencia. Con unión por tamaño y compresión de caminos por mitades, las 2m uniones y las m comprobaciones cuestan O(m α(n)).

Algoritmo

Establece parent[x] = x y anchor[x] = -1 para cada nodo.
Para cada arista [u, v], asigna a cada extremo el otro como su ancla si aún no tiene ninguna.
Combina v con el conjunto de anchor[u], y u con el conjunto de anchor[v].
Devuelve false si alguna arista tiene ambos extremos en un mismo conjunto; de lo contrario, 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

Coloreado en dos colores en anchura de cada parte

Intuición

Un conflicto es definitivo. El primer color de una parte se elige libremente, y cambiarlo cambia el de toda la parte; todos los demás colores quedan determinados por una arista. La búsqueda colorea los nodos según si su distancia desde el inicio es par o impar, así que dos vecinos comparten color solo cuando la parte tiene un ciclo de longitud impar, y entonces no existe ninguna división.

Una búsqueda solo ve su propia parte, así que recorre todos los nodos e inicia una nueva búsqueda desde cada uno que aún no esté coloreado. En el tercer ejemplo, la búsqueda desde el nodo 0 colorea los nodos 0 y 1. La búsqueda desde el nodo 2 asigna el color 0 al nodo 2 y el color 1 a los nodos 3 y 4, después encuentra [3, 4] con el color 1 en ambos extremos: false. Cada nodo se colorea y se pone en cola una vez, y cada una de las 2m entradas de la lista se compara una vez: tiempo y espacio O(n + m).

Algoritmo

Crea listas de adyacencia con cada arista en ambos extremos y asigna -1 a todos los colores.
Para cada nodo sin colorear, en orden, asígnale el color 0 y ponlo en una cola.
Extrae un nodo. Asigna el color opuesto a cada vecino sin colorear y añádelo a la cola; si un vecino tiene el mismo color, devuelve false.
Cuando todas las partes estén coloreadas, devuelve 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

Errores comunes y casos límite

Buscar solo desde el nodo 0. El tercer ejemplo funciona alrededor del nodo 0 y falla entre los nodos 2, 3 y 4.
Agregar cada arista a una sola lista. Con las aristas [1, 0] y [2, 0], el nodo 0 recibe el color 0 y no ve ningún vecino; luego, el nodo 1 también recibe el color 0, y su arista hacia el nodo 0 parece un conflicto, aunque el camino se divide correctamente.
Colorear un nodo al sacarlo de la cola. Entonces, un nodo puede entrar en la cola dos veces, y la segunda visita sobrescribe la primera. Colóralo cuando lo agregues.
Confundir bipartito con acíclico. El cuadrado tiene un ciclo y es bipartito; solo los ciclos impares impiden la división.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Is Graph Bipartite?

Un coloreado en anchura o en profundidad se ejecuta en O(n + m) para m aristas: cada nodo se colorea una vez y cada arista se compara una vez desde cada extremo. Las listas de adyacencia y los colores ocupan O(n + m) espacio. Union-find obtiene la misma respuesta en O(n + m α(n)).

¿Por qué un ciclo impar hace que un grafo no sea bipartito?

Recorre el ciclo y los grupos deben alternarse: primero, segundo, primero, segundo. Un ciclo con un número impar de aristas te devuelve al punto de partida después de un número impar de cambios, por lo que el punto de partida tendría que estar en ambos grupos. Un grafo es bipartito exactamente cuando no tiene ciclos de longitud impar.

¿Deberías usar BFS o DFS para comprobar si un grafo es bipartito?

Ambas opciones funcionan: la regla de coloreado es la misma y solo cambia el orden de visita. En grafos grandes, escribe DFS con una pila explícita, ya que una versión recursiva puede alcanzar una profundidad de una llamada por nodo.

def isBipartite(n, edges):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

true

Is Graph Bipartite

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba todas las divisiones

Union-find en los vecinos de cada nodo

Coloreado en dos colores en anchura de cada parte

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares