Is Graph Bipartite

+10

Um grafo tem n nós, rotulados de 0 a n-1. Cada par [a, b] em edges é uma aresta não direcionada entre o nó a e o nó b. O grafo pode se dividir em várias partes separadas, e alguns nós podem não ter nenhuma aresta.

Um grafo é bipartido quando você consegue dividir seus nós em dois grupos de modo que cada aresta conecte um nó de um grupo a um nó do outro. Retorne true se o grafo for bipartido e false caso contrário.

Função

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

ninteger: o número de nós, numerados de 0 a n-1
edgesinteger-2d-array: as arestas não direcionadas, cada uma sendo um par [a, b]
Retornaboolean: verdadeiro se os nós puderem ser divididos em dois grupos com todas as arestas entre os grupos; caso contrário, falso

Restrições

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] com 0 ≤ a, b ≤ n-1 e a ≠ b
Não há nenhuma aresta que apareça duas vezes, em nenhuma das direções.

Exemplos

Entrada: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Saída: true
Explicação: Coloque os nós 0 e 2 em um grupo e os nós 1 e 3 no outro. Cada uma das quatro arestas conecta os dois grupos.

Entrada: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Saída: false
Explicação: A aresta [0, 1] é dividida corretamente e o nó 5 não tem arestas, mas os nós 2, 3 e 4 formam um triângulo. Basta uma parte que falhe para que a resposta seja false.

Para ir além

Quando o grafo não é bipartido, você consegue retornar um ciclo de comprimento ímpar como prova, listando seus nós em ordem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Escolher um grupo para um nó força o restante da sua parte conectada: um vizinho vai para o outro grupo. Pinte cada parte com uma busca em largura que alterna duas cores; o grafo é bipartido exatamente quando nenhuma aresta tem a mesma cor nas duas extremidades. O grafo pode ser desconexo, então cada nó sem cor inicia uma nova busca.

Experimente cada divisão

Correta, mas não termina nos maiores testes

Intuição

Experimente todas as divisões. Trate o grupo de cada nó como um bit, de modo que os n bits formem um número binário, e contar de 0 a 2^n-1 visita cada divisão uma vez. Para cada divisão, verifique cada aresta e retorne true se alguma divisão fizer com que todas as arestas atravessem os grupos. O número de divisões dobra a cada nó: 20 nós geram cerca de um milhão.

Algoritmo

Para cada número de 0 a 2^n-1, coloque o nó i no grupo indicado pelo bit i.
Se cada aresta conectar os dois grupos, retorne true.
Se nenhuma divisão funcionar, retorne 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 nos vizinhos de cada nó

Intuição

Em qualquer grupo em que um nó fique, todos os seus vizinhos ficam no outro, então eles compartilham um grupo. Para cada nó, una todos os seus vizinhos em um conjunto de union-find; assim, um conjunto contém nós forçados a ficar do mesmo lado. Uma aresta com as duas extremidades em um conjunto é forçada a permanecer dentro de um grupo, portanto o grafo não é bipartido.

Essa verificação detecta todas as falhas. Em torno de um ciclo ímpar, unir duas arestas por vez conecta o primeiro nó ao último, e a aresta de fechamento conecta esses dois. Sem um ciclo ímpar, cada união conecta dois nós a uma distância par, que ficam do mesmo lado. O primeiro vizinho de um nó, sua âncora, identifica o conjunto de seus vizinhos, então você une os nós à medida que as arestas passam, sem listas de adjacência. Com união por tamanho e compressão de caminhos pela metade, as 2m uniões e as m verificações custam O(m α(n)).

Algoritmo

Defina parent[x] = x e anchor[x] = -1 para cada nó.
Para cada aresta [u, v], defina a outra extremidade como âncora de cada extremidade, caso ela ainda não tenha uma.
Una v ao conjunto de anchor[u] e u ao conjunto de anchor[v].
Retorne false se alguma aresta tiver ambas as extremidades no mesmo conjunto; caso contrário, retorne 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

Coloração em duas cores em largura para cada componente

Intuição

Um conflito é conclusivo. A primeira cor de uma componente é uma escolha livre, e invertê-la inverte toda a componente; todas as outras cores são determinadas por uma aresta. A busca colore os nós de acordo com a paridade da distância até o início, então dois vizinhos compartilham uma cor somente quando a componente tem um ciclo de comprimento ímpar, e, nesse caso, não existe divisão.

Uma busca vê apenas sua própria componente, então percorra todos os nós e inicie uma nova busca a partir de cada um que ainda não tenha sido colorido. No terceiro exemplo, a busca a partir do nó 0 colore os nós 0 e 1. A busca a partir do nó 2 atribui a cor 0 ao nó 2 e a cor 1 aos nós 3 e 4, depois encontra [3, 4] com a cor 1 nas duas extremidades: false. Cada nó é colorido e colocado na fila uma vez, e cada uma das 2m entradas da lista é comparada uma vez: tempo e espaço O(n + m).

Algoritmo

Crie listas de adjacência com cada aresta em ambas as extremidades e defina todas as cores como -1.
Para cada nó sem cor, na ordem, atribua a cor 0 e coloque-o em uma fila.
Retire um nó da fila. Atribua a cor oposta a cada vizinho sem cor e coloque-o na fila; se um vizinho tiver a mesma cor, retorne false.
Quando todas as partes estiverem coloridas, retorne 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

Armadilhas e casos extremos

Pesquisar apenas a partir do nó 0. O terceiro exemplo funciona bem em torno do nó 0 e falha entre os nós 2, 3 e 4.
Adicionar cada aresta a apenas uma lista. Com as arestas [1, 0] e [2, 0], o nó 0 recebe a cor 0 e não vê nenhum vizinho; então o nó 1 também recebe a cor 0, e sua aresta até o nó 0 parece causar um conflito, embora o caminho se divida corretamente.
Colorir um nó ao removê-lo da fila. Assim, um nó pode entrar na fila duas vezes, e a segunda visita sobrescreve a primeira. Colora-o ao adicioná-lo.
Confundir bipartido com acíclico. O quadrado tem um ciclo e é bipartido; somente ciclos ímpares impedem a divisão.

Perguntas frequentes3

Qual é a complexidade de tempo de Is Graph Bipartite?

Uma coloração em largura ou em profundidade é executada em O(n + m) para m arestas: cada nó é colorido uma vez, e cada aresta é comparada uma vez a partir de cada extremidade. As listas de adjacência e as cores ocupam O(n + m) de espaço. A estrutura union-find chega à mesma resposta em O(n + m α(n)).

Por que um ciclo ímpar faz com que um grafo não seja bipartido?

Percorra o ciclo, e os grupos devem se alternar: primeiro, segundo, primeiro, segundo. Um ciclo com um número ímpar de arestas faz você voltar ao ponto de partida após um número ímpar de alternâncias, então o ponto de partida teria que estar nos dois grupos. Um grafo é bipartido exatamente quando não tem ciclos de comprimento ímpar.

Você deve usar BFS ou DFS para verificar se um grafo é bipartido?

Ambos funcionam: a regra de coloração é a mesma, e só a ordem de visita muda. Em grafos grandes, escreva o DFS com uma pilha explícita, pois uma versão recursiva pode atingir uma chamada de profundidade por nó.

def isBipartite(n, edges):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

true

Is Graph Bipartite

Função

Restrições

Exemplos

Dicas

Solução

Experimente cada divisão

Union-find nos vizinhos de cada nó

Coloração em duas cores em largura para cada componente

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos