Is Graph Bipartite

+10

Un graphe possède n nœuds, étiquetés de 0 à n-1. Chaque paire [a, b] dans edges représente une arête non orientée entre le nœud a et le nœud b. Le graphe peut être constitué de plusieurs parties distinctes, et certains nœuds peuvent n'avoir aucune arête.

Un graphe est biparti lorsqu'il est possible de répartir ses nœuds en deux groupes de sorte que chaque arête relie un nœud d'un groupe à un nœud de l'autre. Renvoyez true si le graphe est biparti et false dans le cas contraire.

Fonction

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

ninteger: le nombre de nœuds, numérotés de 0 à n-1
edgesinteger-2d-array: les arêtes non orientées, chacune une paire [a, b]
Renvoieboolean: vrai si les nœuds peuvent être répartis en deux groupes avec chaque arête entre les groupes, faux sinon

Contraintes

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] avec 0 ≤ a, b ≤ n-1 et a ≠ b
Aucune arête n'apparaît deux fois, dans l'un ou l'autre sens.

Exemples

Entrée: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Sortie: true
Explication: Placez les nœuds 0 et 2 dans un groupe et les nœuds 1 et 3 dans l’autre. Chacune des quatre arêtes relie les deux groupes.

Entrée: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Sortie: false
Explication: L’arête [0, 1] se divise correctement et le nœud 5 n’a aucune arête, mais les nœuds 2, 3 et 4 forment un triangle. Il suffit qu’une partie échoue pour que la réponse soit false.

Pour aller plus loin

Lorsque le graphe n’est pas biparti, peux-tu renvoyer un cycle de longueur impaire comme preuve, en énumérant ses nœuds dans l’ordre ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Choisir un groupe pour un nœud impose celui du reste de sa composante connexe : un voisin va dans l’autre groupe. Coloriez chaque composante à l’aide d’un parcours en largeur qui alterne deux couleurs ; le graphe est biparti exactement lorsqu’aucune arête n’a la même couleur à ses deux extrémités. Le graphe peut être déconnecté, donc chaque nœud non colorié démarre un nouveau parcours.

Essayez chaque séparation

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Essaie chaque partition. Considère le groupe de chaque nœud comme un bit : les n bits forment alors un nombre binaire, et compter de 0 à 2^n-1 permet de parcourir chaque partition une seule fois. Pour chaque partition, vérifie chaque arête et renvoie true si une partition fait traverser toutes les arêtes. Le nombre de partitions double avec chaque nœud : 20 nœuds en donnent environ un million.

Algorithme

Pour chaque nombre de 0 à 2^n-1, place le nœud i dans le groupe indiqué par le bit i.
Si chaque arête relie les deux groupes, renvoie true.
Si aucune séparation ne fonctionne, renvoie 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 sur les voisins de chaque nœud

Intuition

Quel que soit le groupe dans lequel se trouve un nœud, tous ses voisins se trouvent dans l’autre, donc ils partagent un groupe. Pour chaque nœud, fusionnez tous ses voisins dans un même ensemble union-find ; un ensemble contient alors les nœuds contraints à se trouver du même côté. Une arête dont les deux extrémités appartiennent au même ensemble est contrainte de rester à l’intérieur d’un groupe : le graphe n’est donc pas biparti.

Cette vérification détecte tous les cas d’échec. Autour d’un cycle impair, la fusion de deux arêtes à la fois relie son premier nœud à son dernier, et l’arête qui ferme le cycle relie ces deux nœuds. En l’absence de cycle impair, chaque fusion relie deux nœuds séparés par une distance paire, qui se trouvent du même côté. Le premier voisin d’un nœud, son ancre, désigne l’ensemble de ses voisins ; vous pouvez donc fusionner les ensembles au fil du parcours des arêtes, sans listes d’adjacence. Avec l’union par taille et le raccourcissement des chemins par division en deux, les 2m fusions et les m vérifications coûtent O(m α(n)).

Algorithme

Définissez parent[x] = x et anchor[x] = -1 pour chaque nœud.
Pour chaque arête [u, v], donnez à chaque extrémité l’autre comme ancre si elle n’en a pas encore.
Fusionnez v dans l’ensemble de anchor[u], et u dans l’ensemble de anchor[v].
Renvoyez false si une arête a ses deux extrémités dans le même ensemble, sinon renvoyez 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

Coloration en deux couleurs, en largeur, de chaque partie

Intuition

Un conflit est définitif. La première couleur d’une composante est choisie librement, et l’inverser inverse les couleurs de toute la composante ; toutes les autres couleurs sont imposées par une arête. La recherche colore les nœuds selon que leur distance au point de départ est paire ou impaire. Ainsi, deux voisins ne partagent une couleur que lorsque la composante contient un cycle de longueur impaire, auquel cas aucune séparation n’existe.

Une recherche ne voit que sa propre composante ; parcourez donc tous les nœuds et lancez une nouvelle recherche depuis chacun de ceux qui n’est pas encore coloré. Dans le troisième exemple, la recherche depuis le nœud 0 colore les nœuds 0 et 1. La recherche depuis le nœud 2 attribue la couleur 0 au nœud 2 et la couleur 1 aux nœuds 3 et 4, puis trouve [3, 4] avec la couleur 1 aux deux extrémités : false. Chaque nœud est coloré et ajouté à la file une seule fois, et chacune des 2m entrées de liste est comparée une seule fois : temps et espace en O(n + m).

Algorithme

Construisez des listes d’adjacence en enregistrant chaque arête aux deux extrémités, et définissez chaque couleur à -1.
Pour chaque nœud non coloré, dans l’ordre, attribuez-lui la couleur 0 et placez-le dans une file.
Retirez un nœud de la file. Attribuez à chaque voisin non coloré la couleur opposée et placez-le dans la file ; si un voisin a la même couleur, renvoyez false.
Une fois que chaque partie est colorée, renvoyez 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

Pièges et cas limites

Rechercher uniquement à partir du nœud 0. Le troisième exemple fonctionne autour du nœud 0 et échoue parmi les nœuds 2, 3 et 4.
Ajouter chaque arête à une seule liste. Avec les arêtes [1, 0] et [2, 0], le nœud 0 reçoit la couleur 0 et ne voit aucun voisin ; le nœud 1 reçoit alors lui aussi la couleur 0, et son arête vers le nœud 0 semble créer un conflit, alors que le chemin se divise correctement.
Colorer un nœud quand on le dépile. Un nœud peut alors entrer deux fois dans la file, et la deuxième visite écrase la première. Coloriez-le quand vous l’ajoutez à la file.
Confondre biparti et acyclique. Le carré contient un cycle et est biparti ; seuls les cycles impairs empêchent la division.

Questions fréquentes3

Quelle est la complexité temporelle de « Le graphe est-il biparti ? »

Un parcours en largeur ou en profondeur pour la coloration s’exécute en O(n + m) pour m arêtes : chaque nœud est coloré une fois, et chaque arête est comparée une fois depuis chacune de ses extrémités. Les listes d’adjacence et les couleurs occupent O(n + m) d’espace. La structure union-find permet d’obtenir le même résultat en O(n + m α(n)).

Pourquoi un cycle impair rend-il un graphe non biparti ?

Parcourez le cycle : les groupes doivent alterner : premier, deuxième, premier, deuxième. Un cycle comportant un nombre impair d’arêtes vous ramène au point de départ après un nombre impair de changements, donc le point de départ devrait appartenir aux deux groupes. Un graphe est biparti si et seulement s’il ne contient aucun cycle de longueur impaire.

Faut-il utiliser BFS ou DFS pour vérifier si un graphe est biparti ?

Les deux conviennent : la règle de coloriage est la même, seul l’ordre de visite change. Pour les grands graphes, écris DFS avec une pile explicite, car une version récursive peut s’enfoncer d’un appel par nœud.

def isBipartite(n, edges):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true

Is Graph Bipartite

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque séparation

Union-find sur les voisins de chaque nœud

Coloration en deux couleurs, en largeur, de chaque partie

Pièges et cas limites

Questions fréquentes3

Problèmes similaires