Is Graph Bipartite
Graf ma n węzłów oznaczonych od 0 do n-1. Każda para [a, b] w edges jest nieskierowaną krawędzią między węzłem a a węzłem b. Graf może składać się z kilku oddzielnych części, a niektóre węzły mogą nie mieć żadnej krawędzi.
Graf jest dwudzielny, gdy można podzielić jego węzły na dwie grupy tak, aby każda krawędź łączyła węzeł z jednej grupy z węzłem z drugiej. Zwróć true, jeśli graf jest dwudzielny, a w przeciwnym razie false.
Funkcja
- ninteger
- liczba węzłów, ponumerowanych od 0 do n-1
- edgesinteger-2d-array
- nieskierowane krawędzie, każda w postaci pary [a, b]
- Zwracaboolean
- true, jeśli węzły można podzielić na dwie grupy tak, aby każda krawędź łączyła węzły z różnych grup; w przeciwnym razie false
Ograniczenia
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b], gdzie0 ≤ a, b ≤ n-1oraza ≠ b- Żadna krawędź nie występuje dwukrotnie, w żadnym kierunku.
Przykłady
- Wejście
- n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
- Wyjście
- true
- Wyjaśnienie
- Umieść węzły 0 i 2 w jednej grupie, a węzły 1 i 3 w drugiej. Każda z czterech krawędzi łączy obie grupy.
- Wejście
- n = 3edges = [[0, 1], [1, 2], [2, 0]]
- Wyjście
- false
- Wyjaśnienie
- Węzły 0 i 1 muszą należeć do różnych grup, a węzeł 2 musi różnić się od obu, ale są tylko dwie grupy. Cyklu złożonego z trzech krawędzi nie da się podzielić.
- Wejście
- n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
- Wyjście
- false
- Wyjaśnienie
- Krawędź
[0, 1]dzieli się bez problemu, a węzeł 5 nie ma żadnych krawędzi, ale węzły 2, 3 i 4 tworzą trójkąt. Wystarczy, że jedna część się nie powiedzie, aby odpowiedź była równafalse.
Pytanie dodatkowe
Jeśli graf nie jest dwudzielny, czy możesz zwrócić jeden cykl o nieparzystej długości jako dowód, podając jego węzły w kolejności?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Umieść węzeł 0 w pierwszej grupie. Gdzie muszą trafić jego sąsiedzi? A sąsiedzi tych sąsiadów?
Gdy zostanie umieszczony jeden wierzchołek spójnej części, każdy pozostały wierzchołek tej części nie ma już wyboru: dwa końce krawędzi trafiają do przeciwnych grup. Graf nie spełnia warunku tylko wtedy, gdy takie wymuszone rozmieszczenie umieszcza oba końce jakiejś krawędzi w jednej grupie, co zachodzi dokładnie wtedy, gdy część zawiera cykl o nieparzystej długości.
Koloruj za pomocą wyszukiwania wszerz: nadaj pierwszemu węzłowi części kolor 0, nadaj każdemu niepokolorowanemu sąsiadowi kolor przeciwny do koloru bieżącego węzła i zwróć
false, gdy sąsiad ma już ten sam kolor. Rozpocznij nowe wyszukiwanie od każdego węzła, który nadal nie ma koloru, aby nie pominąć żadnej części.
Rozwiązanie
Przypisanie węzła do jednej grupy wymusza przynależność pozostałej części połączonej z nim: sąsiad trafia do drugiej grupy. Pokoloruj każdą część za pomocą przeszukiwania wszerz, naprzemiennie używając dwóch kolorów; graf jest dwudzielny dokładnie wtedy, gdy żadna krawędź nie łączy dwóch węzłów o tym samym kolorze. Graf może być niespójny, więc każde niepokolorowane węzeł rozpoczyna nowe przeszukiwanie.
Wypróbuj każdy podział
Poprawne, ale nie kończy się na największych testach
Intuicja
Wypróbuj każdy podział. Potraktuj grupę każdego węzła jako jeden bit, tak aby n bitów tworzyło liczbę binarną, a zliczanie od 0 do 2^n-1 pozwala odwiedzić każdy podział dokładnie raz. Dla każdego podziału sprawdź każdą krawędź i zwróć true, jeśli istnieje podział, w którym każda krawędź przebiega między grupami. Liczba podziałów podwaja się wraz z każdym węzłem: 20 węzłów daje około miliona.
Algorytm
- Dla każdej liczby od 0 do 2^n-1 umieść węzeł
iw grupie wskazanej przez biti. - Jeśli każda krawędź łączy obie grupy, zwróć
true. - Jeśli żaden podział nie działa, zwróć
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] = 1Struktura union-find dla sąsiadów każdego węzła
Intuicja
Niezależnie od tego, do której grupy trafi wierzchołek, wszyscy jego sąsiedzi trafiają do drugiej, więc dzielą tę samą grupę. Dla każdego wierzchołka połącz wszystkich jego sąsiadów w jeden zbiór struktury union-find; zbiór zawiera wtedy wierzchołki, które muszą znaleźć się po tej samej stronie. Krawędź, której oba końce należą do jednego zbioru, musi pozostać wewnątrz grupy, więc graf nie jest dwudzielny.
To sprawdzenie wykrywa każdą nieprawidłowość. Wokół nieparzystego cyklu łączenie po dwie krawędzie łączy pierwszy wierzchołek z ostatnim, a krawędź zamykająca cykl łączy te dwa wierzchołki. Jeśli nie ma nieparzystego cyklu, każde łączenie scala dwa wierzchołki oddalone o parzystą odległość, które leżą po tej samej stronie. Pierwszy sąsiad wierzchołka, jego kotwica, wyznacza zbiór jego sąsiadów, więc łączysz je w miarę przetwarzania krawędzi, bez list sąsiedztwa. Łączenie według rozmiaru i spłaszczanie ścieżki przez połowienie sprawiają, że 2m operacji łączenia i m sprawdzeń kosztuje O(m α(n)).
Algorytm
- Ustaw
parent[x] = xianchor[x] = -1dla każdego węzła. - Dla każdej krawędzi
[u, v]ustaw drugi koniec jako punkt zaczepienia każdego końca, który jeszcze go nie ma. - Scal
vze zbioremanchor[u], auze zbioremanchor[v]. - Zwróć
false, jeśli oba końce którejś krawędzi należą do jednego zbioru; w przeciwnym razie zwróć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 TrueDwukolorowanie wszerz każdej części
Intuicja
Konflikt jest rozstrzygający. Pierwszy kolor w części możesz wybrać dowolnie, a jego zmiana odwraca kolory w całej części; każdy pozostały kolor jest wymuszony przez krawędź. Wyszukiwanie koloruje węzły według tego, czy ich odległość od początku jest parzysta, czy nieparzysta, więc sąsiedzi mają ten sam kolor tylko wtedy, gdy część zawiera cykl o nieparzystej długości — a wtedy nie da się jej podzielić.
Wyszukiwanie obejmuje tylko swoją część, więc przejdź przez wszystkie węzły i rozpocznij nowe wyszukiwanie od każdego z nich, który wciąż nie ma koloru. W trzecim przykładzie wyszukiwanie rozpoczęte od węzła 0 koloruje węzły 0 i 1. Wyszukiwanie rozpoczęte od węzła 2 przypisuje węzłowi 2 kolor 0, a węzłom 3 i 4 kolor 1, po czym znajduje [3, 4] z kolorem 1 na obu końcach: false. Każdy węzeł jest kolorowany i dodawany do kolejki raz, a każdy z 2m wpisów na liście jest porównywany raz: czas i pamięć O(n + m).
Algorytm
- Zbuduj listy sąsiedztwa, umieszczając każdą krawędź przy obu jej końcach, i ustaw każdy kolor na -1.
- Dla każdego niepokolorowanego wierzchołka w kolejności przypisz mu kolor 0 i umieść go w kolejce.
- Zdejmij wierzchołek z kolejki. Każdemu niepokolorowanemu sąsiadowi przypisz przeciwny kolor i umieść go w kolejce; jeśli sąsiad ma ten sam kolor, zwróć
false. - Gdy każda część zostanie pokolorowana, zwróć
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
Pułapki i przypadki brzegowe
- Wyszukiwanie tylko od węzła 0. Trzeci przykład działa w okolicy węzła 0, ale zawodzi wśród węzłów 2, 3 i 4.
- Dodawanie każdej krawędzi tylko do jednej listy. Przy krawędziach
[1, 0]i[2, 0]węzeł 0 otrzymuje kolor 0 i nie widzi żadnych sąsiadów; następnie węzeł 1 również otrzymuje kolor 0, a jego krawędź do węzła 0 wygląda na konflikt, chociaż podział ścieżki działa poprawnie. - Kolorowanie węzła podczas zdejmowania go z kolejki. Węzeł może wtedy trafić do kolejki dwa razy, a druga wizyta nadpisze pierwszą. Koloruj go podczas dodawania do kolejki.
- Mylenie grafu dwudzielnego z acyklicznym. Kwadrat ma cykl i jest dwudzielny; tylko cykle nieparzyste uniemożliwiają podział.
Najczęstsze pytania3
Jaka jest złożoność czasowa algorytmu Is Graph Bipartite?
Kolorowanie wszerz lub w głąb działa w czasie O(n + m) dla m krawędzi: każdy węzeł jest kolorowany raz, a każda krawędź jest porównywana raz z każdego końca. Listy sąsiedztwa i kolory zajmują O(n + m) miejsca. Struktura Union-Find uzyskuje tę samą odpowiedź w czasie O(n + m α(n)).
Dlaczego nieparzysty cykl sprawia, że graf nie jest dwudzielny?
Przejdź wzdłuż cyklu, a grupy muszą się zmieniać naprzemiennie: pierwsza, druga, pierwsza, druga. Cykl o nieparzystej liczbie krawędzi prowadzi z powrotem do punktu wyjścia po nieparzystej liczbie zmian, więc punkt wyjścia musiałby należeć do obu grup. Graf jest dwudzielny wtedy i tylko wtedy, gdy nie zawiera cyklu o nieparzystej długości.
Czy użyć BFS czy DFS, aby sprawdzić, czy graf jest dwudzielny?
Oba rozwiązania działają: zasada kolorowania jest taka sama, zmienia się tylko kolejność odwiedzania. W przypadku dużych grafów napisz DFS z jawnym stosem, ponieważ wersja rekurencyjna może zagłębić się o jedno wywołanie na każdy węzeł.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def isBipartite(n, edges):
# Napisz kod tutajTest #1
Test #2
Test #3
Argumenty
n = 4 edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Oczekiwany wynik
true