Redundant Connection
Sieć początkowo miała postać drzewa: n węzłów, ponumerowanych od 1 do n, połączonych n-1 nieskierowanymi krawędziami bez cykli. Następnie dodano jeszcze jedną krawędź między dwoma węzłami, które nie były bezpośrednio połączone, więc lista edges zawiera teraz n krawędzi i dokładnie jeden cykl.
Zwróć krawędź, którą możesz usunąć, aby pozostałe n-1 krawędzi ponownie utworzyły drzewo. Jeśli pasuje kilka krawędzi, zwróć tę, która występuje najpóźniej w edges, jako parę [a, b] dokładnie w takiej postaci, w jakiej została tam zapisana.
Funkcja
- edgesinteger-2d-array
- n nieskierowanych krawędzi, z których każda jest parą [a, b] węzłów ponumerowanych od 1
- Zwracainteger-array
- krawędź cyklu, która pojawia się jako ostatnia w edges, zapisana tak, jak tam występuje
Ograniczenia
3 ≤ n ≤ 5000, gdzien = edges.lengthedges[i] = [a, b], gdzie1 ≤ a, b ≤ noraza ≠ b- Żadna krawędź nie występuje dwukrotnie, w żadnym kierunku.
- Krawędzie łączą wszystkie
nwęzłów i tworzą dokładnie jeden cykl.
Przykłady
- Wejście
- edges = [[1, 2], [1, 3], [2, 3]]
- Wyjście
- [2, 3]
- Wyjaśnienie
- Trzy krawędzie tworzą trójkąt 1, 2, 3, więc usunięcie dowolnej z nich pozostawia drzewo.
[2, 3]znajduje się na końcu listy.
- Wejście
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Wyjście
- [1, 4]
- Wyjaśnienie
- Cykl to 1, 2, 3, 4, 1. Krawędź
[1, 5]nie należy do niego: jej usunięcie odcięłoby węzeł 5. Spośród czterech krawędzi cyklu[1, 4]występuje jako ostatnia.
Pytanie dodatkowe
Jeśli krawędzie byłyby skierowane, a pierwotny graf byłby drzewem ukorzenionym, którą krawędź usunąłbyś, gdy dodatkowa krawędź sprawia, że węzeł ma dwóch rodziców?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Po usunięciu krawędzi wszystkie węzły
nmuszą pozostać połączone. Które krawędzie możesz usunąć, nie dzieląc grafu na dwie części?Tylko krawędzie cyklu: każda z nich ma drugą trasę wokół cyklu, a każda pozostała krawędź jest jedynym połączeniem z jakąś częścią grafu. Zatem odpowiedzią jest krawędź cyklu, która znajduje się najpóźniej na liście.
Dodawaj krawędzie w kolejności z listy do
nodrębnych grup. Pierwsza krawędź, której oba końce są już w tej samej grupie, zamyka cykl, a każda pozostała krawędź cyklu pojawiła się przed nią. Struktura union-find znajduje tę krawędź w jednym przebiegu.
Rozwiązanie
Usunięcie krawędzi pozostawia drzewo dokładnie wtedy, gdy krawędź należy do jedynego cyklu grafu, więc odpowiedzią jest krawędź cyklu, która występuje najpóźniej na liście. Struktura union-find znajduje ją w jednym przebiegu: dodawaj krawędzie po kolei, a pierwsza krawędź, której końce są już połączone, jest odpowiedzią.
Spróbuj usuwać każdą krawędź, zaczynając od ostatniej
Poprawne, ale nie kończy się na największych testach
Intuicja
Usuń jedną krawędź i sprawdź, czy pozostałe n-1 krawędzie tworzą drzewo. Przy n węzłach i n-1 krawędziach dzieje się tak dokładnie wtedy, gdy jedno przeszukiwanie od węzła 1 dociera do wszystkich n węzłów. Sprawdzaj krawędzie od końca listy, aby pierwsze usunięcie, które przejdzie test, było tym najpóźniejszym. Zapisz indeks każdej krawędzi na listach sąsiedztwa, a przeszukiwanie będzie mogło pominąć usuniętą krawędź bez przebudowywania czegokolwiek.
Każda próba wymaga pełnego przeszukiwania O(n), a prób może być n: do 2.5 × 10^7 kroków, gdy n = 5000.
Algorytm
- Zbuduj listy sąsiedztwa, które dla każdego sąsiada przechowują indeks prowadzącej do niego krawędzi.
- Dla
skip, zaczynając od ostatniego indeksu i cofając się do 0, rozpocznij wyszukiwanie od węzła 1 i pomiń krawędź o indeksieskip. - Policz węzły osiągnięte przez wyszukiwanie.
- Jeśli osiągnie wszystkie
n, zwróćedges[skip].
def findRedundantConnection(edges):
n = len(edges)
# graph[x] holds (neighbour, index of the edge) for every edge at node x.
graph = [[] for _ in range(n + 1)]
for i, (u, v) in enumerate(edges):
graph[u].append((v, i))
graph[v].append((u, i))
# Try leaving out each edge, the last one first.
for skip in range(n - 1, -1, -1):
# Without edge skip, can node 1 still reach all n nodes?
seen = [False] * (n + 1)
seen[1] = True
stack = [1]
reached = 1
while stack:
node = stack.pop()
for nxt, i in graph[node]:
if i != skip and not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
# n-1 edges that connect n nodes form a tree.
if reached == n:
return edges[skip]
return []Obierz liście
Intuicja
Liść, czyli węzeł z jedną krawędzią, nie może należeć do cyklu, ponieważ cykl wchodzi do każdego ze swoich węzłów i z niego wychodzi. Usunięcie liścia może sprawić, że jego sąsiad stanie się liściem, więc usuwaj je kolejno, aż żaden nie pozostanie. To, co zostanie, to dokładnie cykl, ponieważ każdy jego węzeł zachowuje swoje dwie krawędzie cyklu. W drugim przykładzie usuwany jest węzeł 5, węzeł 1 zachowuje dwie krawędzie, a pozostają węzły od 1 do 4.
Każda krawędź między dwoma pozostałymi węzłami należy do cyklu, ponieważ drugie połączenie między węzłami cyklu utworzyłoby drugi cykl. Dlatego przejdź po edges od końca i zwróć pierwszą krawędź, której oba końce pozostały.
Algorytm
- Zbuduj listy sąsiedztwa i policz stopień każdego wierzchołka.
- Umieść na stosie każdy wierzchołek o stopniu 1.
- Zdejmij liść ze stosu, ustaw jego stopień na 0 i zmniejsz stopień jego pozostałego sąsiada; umieść tego sąsiada na stosie, gdy jego stopień spadnie do 1.
- Gdy stos będzie pusty, wierzchołki o stopniu większym od 0 utworzą cykl.
- Przejdź po
edgesod końca i zwróć pierwszą krawędź, której oba końce nadal pozostają.
def findRedundantConnection(edges):
n = len(edges)
graph = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
# A node with one edge cannot lie on the cycle. Remove it, and repeat.
stack = [x for x in range(1, n + 1) if degree[x] == 1]
while stack:
leaf = stack.pop()
degree[leaf] = 0
for nxt in graph[leaf]:
if degree[nxt] > 0:
degree[nxt] -= 1
if degree[nxt] == 1:
stack.append(nxt)
# Only the cycle is left. Its edge that comes last in the list is the answer.
for u, v in reversed(edges):
if degree[u] > 0 and degree[v] > 0:
return [u, v]
return []Union-find: pierwsza krawędź zamykająca pętlę
Intuicja
Dodawaj krawędzie w kolejności z listy i śledź, które węzły są połączone. Dopóki cykl się nie zamknie, każda krawędź łączy dwie części, między którymi nie ma ścieżki. Pierwsza krawędź, której końce są już połączone, zamyka cykl. Pozostałe krawędzie cyklu dodano wcześniej, więc krawędź zamykająca cykl pojawia się jako ostatnia. W drugim przykładzie [1, 4] wskazuje, że węzły 1 i 4 są już połączone, a [1, 5] nigdy nie zostaje odczytana.
Struktura union-find przechowuje jedną tablicę, parent; podążanie wskaźnikami od węzła prowadzi do korzenia jego części. Dołączanie mniejszej części do większej i wskazywanie przez węzły ich dziadków podczas find utrzymuje krótkie łańcuchy. Koszt każdej operacji wynosi wtedy zamortyzowane O(α(n)), gdzie α, odwrotna funkcja Ackermanna, ma wartość co najwyżej 4 dla każdego rzeczywistego wejścia.
Algorytm
- Wskaż każdy węzeł od 1 do
nna samego siebie,parent[x] = x, i ustaw jego rozmiar na 1. - Przejdź po
edgesw kolejności. Dla[u, v]znajdź korzeńui korzeńv. - Jeśli korzenie są takie same,
[u, v]zamyka cykl: zwróć tę krawędź w podanej postaci. - Jeśli nie, większa część wchłania mniejszą: jej korzeń staje się rodzicem mniejszego korzenia, a rozmiary się sumują.
def findRedundantConnection(edges):
n = len(edges)
parent = list(range(n + 1)) # every node starts as its own group
size = [1] * (n + 1)
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
for u, v in edges:
a, b = find(u), find(v)
# u and v are already connected: this edge closes the cycle.
if a == b:
return [u, v]
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return []
Pułapki i przypadki brzegowe
- Zwracanie ostatniej krawędzi listy. W drugim przykładzie jest to
[1, 5], a jej usunięcie odcina węzeł 5. - Przeszukiwanie od początku po odcięciu. Zwraca to najwcześniejszą krawędź cyklu, czyli
[1, 2]w drugim przykładzie. - Sortowanie lub odwracanie pary. Jeśli lista zawiera
[3, 1], zwróć[3, 1], a nie[1, 3]. - Przydzielanie tablic o rozmiarze wystarczającym dla węzłów od 0 do
n-1. Węzły są numerowane od 1, więc węzełnwymaga tablicy zn+1miejscami. - Rekurencyjne przechodzenie cyklu. Może ono przechodzić przez wszystkie 5000 węzłów, czyli pięć razy więcej niż domyślny limit rekurencji Pythona, więc użyj jawnego stosu i pętli w
find.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu Redundant Connection?
Union-find rozwiązuje ten problem w jednym przebiegu po n krawędziach: czas O(n · α(n)), gdzie α(n) w praktyce wynosi co najwyżej 4, i pamięć O(n). Usuwanie liści również zajmuje O(n). Próbowanie każdego usunięcia z nowym wyszukiwaniem kosztuje O(n²).
Które krawędzie można usunąć, aby pozostało drzewo?
Dokładnie krawędzie cyklu. Każda z nich ma drugą trasę między swoimi końcami, prowadzącą przez pozostałą część cyklu, więc jej usunięcie zachowuje spójność grafu. Każda inna krawędź jest jedynym połączeniem między dwiema częściami grafu, a jej usunięcie rozdziela je.
Czy problem Redundant Connection można rozwiązać za pomocą DFS?
Tak. Przed dodaniem każdej krawędzi przeszukaj graf od jednego końca, korzystając z dotychczas dodanych krawędzi; pierwsza krawędź, której drugi koniec jest już osiągalny, stanowi odpowiedź. Kosztuje to O(n) na krawędź, czyli łącznie O(n²), podczas gdy struktura union-find odpowiada na to samo pytanie w czasie bliskim stałemu.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def findRedundantConnection(edges):
# Wpisz kod tutajTest #1
Test #2
Argument
edges = [[1, 2], [1, 3], [2, 3]]
Oczekiwany wynik
[2, 3]