Is Graph Bipartite

+10

Un grafo ha n nodi, etichettati da 0 a n-1. Ogni coppia [a, b] in edges rappresenta un arco non orientato tra il nodo a e il nodo b. Il grafo può essere suddiviso in diverse parti separate e alcuni nodi potrebbero non avere alcun arco.

Un grafo è bipartito quando puoi dividere i suoi nodi in due gruppi in modo che ogni arco colleghi un nodo di un gruppo a un nodo dell'altro. Restituisci true se il grafo è bipartito e false altrimenti.

Funzione

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

ninteger: il numero di nodi, numerati da 0 a n-1
edgesinteger-2d-array: gli archi non orientati, ciascuno una coppia [a, b]
Restituisceboolean: vero se i nodi possono essere suddivisi in due gruppi con ogni arco tra i gruppi, falso altrimenti

Vincoli

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] con 0 ≤ a, b ≤ n-1 e a ≠ b
Nessun arco compare due volte, in nessuna delle due direzioni.

Esempi

Input: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: true
Spiegazione: Metti i nodi 0 e 2 in un gruppo e i nodi 1 e 3 nell’altro. Ognuno dei quattro archi collega i due gruppi.

Input: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Output: false
Spiegazione: L'arco [0, 1] si divide correttamente e il nodo 5 non ha archi, ma i nodi 2, 3 e 4 formano un triangolo. Basta una parte che non funziona per rendere la risposta false.

Per approfondire

Quando il grafo non è bipartito, riesci a restituire un ciclo di lunghezza dispari come prova, elencandone i nodi in ordine?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Scegliere un gruppo per un nodo determina il resto della sua componente connessa: un nodo adiacente va nell’altro gruppo. Colora ogni componente con una ricerca in ampiezza che alterna due colori; il grafo è bipartito esattamente quando nessun arco ha lo stesso colore a entrambe le estremità. Il grafo può essere sconnesso, quindi ogni nodo non colorato avvia una nuova ricerca.

Prova ogni suddivisione

Corretto, ma non termina sui test più grandi

Intuizione

Prova ogni suddivisione. Tratta il gruppo di ciascun nodo come un bit, così gli n bit formano un numero binario e contando da 0 a 2^n-1 si visita ogni suddivisione una volta. Per ogni suddivisione, controlla ogni arco e restituisci true se esiste una suddivisione in cui ogni arco attraversa i gruppi. Le suddivisioni raddoppiano a ogni nodo: 20 nodi ne generano circa un milione.

Algoritmo

Per ogni numero da 0 a 2^n-1, inserisci il nodo i nel gruppo indicato dal bit i.
Se ogni arco collega i due gruppi, restituisci true.
Se nessuna divisione funziona, restituisci 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 sui vicini di ciascun nodo

Intuizione

Qualunque sia il gruppo in cui finisce un nodo, tutti i suoi vicini finiscono nell'altro, quindi condividono un gruppo. Per ogni nodo, unisci tutti i suoi vicini in un unico insieme union-find; un insieme contiene quindi nodi costretti a stare dallo stesso lato. Un arco con entrambe le estremità in un unico insieme è costretto a rimanere all'interno di un gruppo, quindi il grafo non è bipartito.

Il controllo rileva ogni caso di fallimento. Intorno a un ciclo dispari, unire due archi alla volta collega il primo nodo con l'ultimo, e l'arco di chiusura unisce questi due. In assenza di cicli dispari, ogni unione collega due nodi a distanza pari, che si trovano dallo stesso lato. Il primo vicino di un nodo, il suo punto di riferimento, identifica l'insieme dei suoi vicini, quindi puoi eseguire le unioni man mano che scorrono gli archi, senza liste di adiacenza. Con l'unione per dimensione e la compressione dimezzata dei cammini, le 2m unioni e i m controlli hanno un costo di O(m α(n)).

Algoritmo

Imposta parent[x] = x e anchor[x] = -1 per ogni nodo.
Per ogni arco [u, v], assegna a ciascuna estremità l’altra come ancora, se non ne ha ancora una.
Unisci v all’insieme di anchor[u] e u all’insieme di anchor[v].
Restituisci false se un arco ha entrambe le estremità nello stesso insieme, altrimenti 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

Colorazione a due colori in ampiezza di ogni parte

Intuizione

Un conflitto è definitivo. Il primo colore di una componente è scelto liberamente e invertirlo inverte l’intera componente; ogni altro colore è imposto da un arco. La ricerca assegna i colori ai nodi in base al fatto che la loro distanza dall’inizio sia pari o dispari, quindi due nodi adiacenti condividono un colore solo quando la componente contiene un ciclo di lunghezza dispari: in tal caso non esiste alcuna suddivisione.

Una ricerca vede solo la propria componente, quindi esamina tutti i nodi e avvia una nuova ricerca da ciascuno di quelli ancora senza colore. Nel terzo esempio, la ricerca dal nodo 0 assegna i colori ai nodi 0 e 1. La ricerca dal nodo 2 assegna al nodo 2 il colore 0 e ai nodi 3 e 4 il colore 1, poi trova [3, 4] con il colore 1 a entrambe le estremità: false. Ogni nodo viene colorato e inserito in coda una sola volta, e ciascuna delle 2m voci degli elenchi viene confrontata una volta: tempo e spazio O(n + m).

Algoritmo

Crea liste di adiacenza con ogni arco associato a entrambi gli estremi e imposta ogni colore a -1.
Per ogni nodo non colorato, nell’ordine, assegnagli il colore 0 e inseriscilo in una coda.
Estrai un nodo. Assegna a ogni vicino non colorato il colore opposto e inseriscilo nella coda; se un vicino ha lo stesso colore, restituisci false.
Una volta colorate tutte le parti, restituisci 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

Trappole e casi limite

Cercare solo a partire dal nodo 0. Il terzo esempio funziona intorno al nodo 0 e fallisce tra i nodi 2, 3 e 4.
Aggiungere ogni arco a una sola lista. Con gli archi [1, 0] e [2, 0], il nodo 0 riceve il colore 0 e non vede vicini; anche il nodo 1 riceve quindi il colore 0 e il suo arco verso il nodo 0 sembra causare un conflitto, anche se il percorso si divide correttamente.
Colorare un nodo quando lo estrai dalla coda. In questo modo, un nodo può entrare nella coda due volte e la seconda visita sovrascrive la prima. Coloralo quando lo inserisci.
Confondere bipartito con aciclico. Il quadrato ha un ciclo ed è bipartito; solo i cicli dispari impediscono la divisione.

Domande frequenti3

Qual è la complessità temporale di Is Graph Bipartite?

Una colorazione in ampiezza o in profondità ha complessità O(n + m) per m archi: ogni nodo viene colorato una volta e ogni arco viene confrontato una volta da ciascuna estremità. Le liste di adiacenza e i colori occupano O(n + m) spazio. Union-find raggiunge lo stesso risultato in O(n + m α(n)).

Perché un ciclo dispari rende un grafo non bipartito?

Percorri il ciclo e i gruppi devono alternarsi: primo, secondo, primo, secondo. Un ciclo con un numero dispari di archi ti riporta al punto di partenza dopo un numero dispari di cambi, quindi il punto di partenza dovrebbe appartenere a entrambi i gruppi. Un grafo è bipartito se e solo se non contiene cicli di lunghezza dispari.

Dovresti usare BFS o DFS per verificare se un grafo è bipartito?

Vanno bene entrambi: la regola di colorazione è la stessa e cambia solo l’ordine di visita. Nei grafi grandi, scrivi la DFS usando uno stack esplicito, perché una versione ricorsiva può arrivare a una chiamata in profondità per ogni nodo.

def isBipartite(n, edges):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

true

Is Graph Bipartite

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni suddivisione

Union-find sui vicini di ciascun nodo

Colorazione a due colori in ampiezza di ogni parte

Trappole e casi limite

Domande frequenti3

Problemi simili