Strongly Connected Components
Graf skierowany ma n węzłów, ponumerowanych od 0 do n-1, oraz listę edges, gdzie [from, to] oznacza krawędź od węzła from do węzła to.
Silnie spójna składowa to największa grupa węzłów, w której każdy węzeł może dotrzeć do każdego innego, podążając wzdłuż krawędzi. Każdy węzeł należy dokładnie do jednej składowej, a węzeł, który nie leży na żadnym cyklu, tworzy składową samodzielnie. Zwróć liczbę silnie spójnych składowych.
Funkcja
- ninteger
- liczba węzłów
- edgesinteger-2d-array
- krawędzie skierowane, każda jako [from, to]
- Zwracainteger
- liczba silnie spójnych składowych
Ograniczenia
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]dla0 ≤ from, to < norazfrom ≠ to- Żadna krawędź nie pojawia się dwa razy.
Przykłady
- Wejście
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Wyjście
- 3
- Wyjaśnienie
- Węzły 0, 1 i 2 tworzą pętlę, więc docierają do siebie nawzajem. Węzły 3 i 4 wskazują na siebie nawzajem. Z węzła 5 można dotrzeć do 4, ale nic nie wraca do 5, więc pozostaje on samodzielny: 3 składowe.
- Wejście
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Wyjście
- 4
- Wyjaśnienie
- Węzły 0 i 1 wskazują na siebie nawzajem i tworzą jeden komponent. Krawędź od 2 do 3 prowadzi tylko w jedną stronę, więc 2 i 3 są oddzielne, a węzeł 4 nie ma żadnych krawędzi: 4 komponenty.
Pytanie dodatkowe
Ile krawędzi trzeba dodać, aby cały graf stał się jedną silnie spójną składową?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Dwa węzły należą do tej samej składowej dokładnie wtedy, gdy każdy z nich może dotrzeć do drugiego. Można to sprawdzić, rozpoczynając przeszukiwanie z każdego węzła, ale w ten sposób te same krawędzie są przemierzane wielokrotnie. Co pojedyncze przeszukiwanie w głąb może powiedzieć o tym, gdzie zaczyna się składowa?
Ponumeruj węzły w kolejności, w jakiej po raz pierwszy dociera do nich wyszukiwanie w głąb. Dla każdego węzła śledź też
low: najmniejszy numer, do którego może dotrzeć, schodząc w dół drzewa wyszukiwania, a następnie przechodząc jedną krawędzią z powrotem do węzła, którego komponent jest nadal otwarty. Węzeł, któregolowjest równy jego własnemu numerowi, jest pierwszym węzłem swojego komponentu.Przechowuj odwiedzone węzły na stosie. Gdy węzeł kończy działanie z wartością
lowrówną jego własnemu numerowi, zdejmij ze stosu elementy aż do tego węzła: te węzły tworzą jedną składową, więc ją policz. Jeden z testów sprawia, że wyszukiwanie osiąga głębokość 5000 węzłów, dlatego zamiast rekurencji użyj własnego stosu ramek (węzeł, następna krawędź).
Rozwiązanie
Zmniejsz każdy komponent do punktu, a komponenty utworzą graf bez cykli. Algorytmy Kosaraju i Tarjana wykorzystują to, aby znaleźć każdy komponent w czasie O(n + E), gdzie E to liczba krawędzi.
Szukaj w przód i w tył od każdego węzła
Poprawne, ale nie kończy się na największych testach
Intuicja
Węzły u i v należą do tej samej składowej dokładnie wtedy, gdy każdy z nich może dotrzeć do drugiego. Dla węzła s, który nie należy jeszcze do żadnej składowej, przeszukaj graf wzdłuż krawędzi w przód oraz wzdłuż odwróconych krawędzi wstecz. Węzły znalezione podczas obu przeszukiwań tworzą jego składową. W pierwszym przykładzie, przeszukiwanie w przód od 0 znajduje węzły od 0 do 4, a przeszukiwanie wstecz znajduje 0, 1 i 2, więc {0, 1, 2} to jedna składowa.
Każda składowa wymaga dwóch przeszukiwań obejmujących większość grafu. W łańcuchu z 5000 krawędziami i 5001 węzłami każdy węzeł tworzy osobną składową, a przeszukiwania odwiedzają około 2.5 × 10^7 węzłów.
Algorytm
- Zbuduj listy krawędzi wychodzących i wchodzących dla każdego węzła.
- Weź następny węzeł
s, który nie należy do żadnej składowej, i zwiększ licznik składowych. - Oznacz węzły, do których można dotrzeć z
swzdłuż krawędzi wychodzących, oraz te, z których można dotrzeć doswzdłuż krawędzi wchodzących. - Każdy węzeł oznaczony przez oba przeszukiwania dołącza do składowej
s. Gdy każdy węzeł będzie już przypisany, zwróć licznik.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countAlgorytm Kosaraju: dwa przejścia
Intuicja
W grafie składowych pewna składowa jest ujściem, z którego nie wychodzi żadna krawędź, a wyszukiwanie rozpoczęte w jej wnętrzu znajduje dokładnie tę składową. Algorytm Kosaraju porządkuje wyszukiwania tak, by każde z nich zachowywało się właśnie w ten sposób.
Pierwsze przejście wypisuje każdy wierzchołek w chwili zakończenia jego przeszukiwania w głąb. Drugie przejście przeszukuje graf odwrócony, który ma te same składowe, rozpoczynając od wierzchołka, którego przeszukiwanie zakończyło się jako ostatnie. Jeśli krawędź prowadzi ze składowej B do C, ostatni wierzchołek B kończy przeszukiwanie po wszystkich wierzchołkach C. Dlatego gdy drugie przejście dociera do C, wszystkie składowe z krawędzią prowadzącą do C są już przypisane, a w grafie odwróconym przeszukiwanie nie może opuścić C.
W pierwszym przykładzie wierzchołki kończą przeszukiwanie w kolejności 4, 3, 2, 1, 0, 5. Drugie przejście zbiera {5}, następnie {0, 1, 2}, a potem {3, 4}.
Algorytm
- Zbuduj listy krawędzi wychodzących i wchodzących.
- Uruchom iteracyjne przeszukiwanie w głąb z każdego nieodwiedzonego węzła i dodaj każdy węzeł do
orderpo jego przetworzeniu. - Przejdź przez
orderod końca. Dla każdego węzła, który nie należy do żadnej składowej, zwiększ licznik i przeszukaj graf od tego węzła wzdłuż krawędzi wchodzących, przypisując każdy nieprzypisany węzeł, do którego dotrzesz. Zwróć licznik.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countAlgorytm Tarjana: jedno przejście z wartościami low
Intuicja
Wykonaj jedno wyszukiwanie w głąb i ponumeruj każdy węzeł w kolejności, w jakiej do niego dotrzesz: jego index. Zachowuj stos odwiedzonych węzłów, których składowa jest nadal otwarta, oraz wartość low: najmniejszy indeks, do którego węzeł może dotrzeć, schodząc w dół drzewa wyszukiwania, a następnie cofając się jedną krawędzią do węzła na tym stosie.
Gdy przetwarzanie węzła się kończy i jego low jest mniejsze niż index, coś poniżej niego wraca do wcześniejszego, otwartego węzła, więc pozostaje on na stosie. Gdy są równe, węzeł jest pierwszym, do którego wyszukiwanie dotarło w jego składowej: zdejmuj węzły ze stosu aż do niego i zwiększ licznik składowych o jeden. Krawędź prowadząca do zdjętego ze stosu węzła prowadzi do zakończonej składowej, która nie może dotrzeć z powrotem, więc jest ignorowana.
W pierwszym przykładzie węzeł 3 zdejmuje ze stosu {4, 3}, a węzeł 0 — {2, 1, 0}. Krawędź z węzła 5 prowadzi do zdjętego ze stosu węzła 4, więc węzeł 5 zostaje zdjęty sam.
Algorytm
- Dla każdego nieodwiedzonego węzła nadaj mu kolejny indeks, ustaw
lowna tę samą wartość, umieść go na stosie węzłów i umieść na stosie ramkę (węzeł, pierwsza krawędź). - Jeśli węzeł z górnej ramki ma jeszcze krawędź, podążaj nią: nieodwiedzony cel otrzymuje indeks i ramkę, a cel znajdujący się na stosie węzłów obniża
low[node]do swojego indeksu. - W przeciwnym razie zdejmij ramkę ze stosu i obniż wartość
lowrodzica dolow[node]. Jeślilow[node]jest równeindex[node], zdejmuj węzły ze stosu aż do tego węzła i policz jedną składową.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Pułapki i przypadki brzegowe
- Pomijanie wierzchołków bez krawędzi. W drugim przykładzie wierzchołek 4 nie występuje w żadnej krawędzi, a mimo to jest składową.
- Obniżanie
lowprzez dowolny odwiedzony wierzchołek zamiast tylko przez te znajdujące się na stosie. W pierwszym przykładzie krawędź5 → 4nie pozwala wtedy wierzchołkowi 5 zamknąć swojej składowej. - Traktowanie krawędzi jako dwukierunkowych. W ten sposób liczy się składowe spójne: pierwszy przykład dałby 1 zamiast 3.
- Używanie rekurencji w Pythonie. Cykl przechodzący przez 5000 wierzchołków tworzy 5000 zagnieżdżonych wywołań, czyli pięć razy więcej niż domyślny limit wynoszący 1000. Użyj własnego stosu ramek.
- Uruchamianie drugiego przebiegu algorytmu Kosaraju na oryginalnych krawędziach lub w kolejności pierwszego odwiedzenia wierzchołków. Każde z tych podejść łączy składowe, między którymi istnieje ścieżka tylko w jednym kierunku.
Najczęstsze pytania3
Jaka jest złożoność czasowa znajdowania silnie spójnych składowych?
Czas O(n + E) w przypadku algorytmu Kosaraju lub Tarjana, ponieważ każdy węzeł i każda krawędź są obsługiwane stałą liczbę razy. Oba algorytmy wymagają O(n + E) pamięci na listy krawędzi i stosy przeszukiwania.
Czy należy użyć algorytmu Kosaraju czy Tarjana?
Algorytm Kosaraju to dwa proste przeszukiwania i trudniej popełnić w nim błąd. Algorytm Tarjana wymaga jednego przeszukiwania i nie potrzebuje odwróconego grafu, ale trzeba w nim śledzić wartości low.
Jaka jest różnica między silnie spójnymi składowymi a spójnymi składowymi?
Składowe spójne ignorują kierunek krawędzi: dwa węzły należą do tej samej składowej, gdy łączy je jakaś ścieżka. W składowych silnie spójnych każdy węzeł musi być osiągalny z każdego innego. Pierwszy przykład przedstawia jedną składową spójną, ale trzy składowe silnie spójne.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def countSCC(n, edges):
# Napisz kod tutajTest #1
Test #2
Argumenty
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Oczekiwany wynik
3