Redundant Connection
Bir ağ başlangıçta bir ağaçtı: 1 ile n arasında numaralandırılmış n düğüm, döngü içermeyen n-1 yönsüz kenarla birbirine bağlıydı. Ardından, doğrudan bağlı olmayan iki düğüm arasına bir kenar daha eklendi; böylece edges listesi artık n kenar içeriyor ve tam olarak bir döngü barındırıyor.
Diğer n-1 kenarın yeniden bir ağaç oluşturması için kaldırabileceğiniz bir kenarı döndürün. Birden fazla kenar uygunsa, edges içinde en son görüneni, orada yazıldığı biçimiyle tam olarak [a, b] çifti olarak döndürün.
Fonksiyon
- edgesinteger-2d-array
- n yönsüz kenar; her biri, 1'den başlayarak numaralandırılmış düğümlerden oluşan [a, b] çiftidir
- Döndürürinteger-array
- edges içinde en son görünen, orada yazıldığı şekliyle çevrim kenarı
Kısıtlar
3 ≤ n ≤ 5000, buradan = edges.lengthedges[i] = [a, b]olacak şekilde1 ≤ a, b ≤ nvea ≠ b- Hiçbir kenar, yön fark etmeksizin iki kez görünmez.
- Kenarlar tüm
ndüğümü birbirine bağlar ve tam olarak bir döngü içerir.
Örnekler
- Girdi
- edges = [[1, 2], [1, 3], [2, 3]]
- Çıktı
- [2, 3]
- Açıklama
- Üç kenar 1, 2, 3 üçgenini oluşturur, bu yüzden bunlardan herhangi birini kaldırmak bir ağaç bırakır.
[2, 3]listedeki son öğedir.
- Girdi
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Çıktı
- [1, 4]
- Açıklama
- Döngü 1, 2, 3, 4, 1 şeklindedir.
[1, 5]kenarı bu döngüde değildir: onu kaldırmak 5. düğümün bağlantısını keser. Döngüdeki dört kenar arasında[1, 4]en son görünür.
Ek soru
Halkalar yönlendirilmiş ve özgün grafik köklü bir ağaç olsaydı, fazladan kenar bir düğüme iki ebeveyn verdiğinde hangi kenarı kaldırırdınız?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Kenar kaldırıldığında tüm
ndüğüm bağlantılı kalmalıdır. Grafiği ikiye bölmeden hangi kenarları kaldırabilirsiniz?Yalnızca döngüdeki kenarlar: Her birinin döngü boyunca ikinci bir yolu vardır ve diğer tüm kenarlar grafiğin bir bölümüne giden tek bağlantıdır. Dolayısıyla cevap, listedeki son döngü kenarıdır.
Kenarları, listedeki sırayla
nayrı gruba ekle. İki ucu da zaten aynı grupta olan ilk kenar çevrimi kapatır ve çevrimdeki diğer tüm kenarlar ondan önce gelir. Bir union-find bu kenarı tek geçişte bulur.
Çözüm
Bir kenarın kaldırılması, yalnızca bu kenar grafın tek çevrimi üzerinde yer alıyorsa bir ağaç bırakır; dolayısıyla yanıt, listede en son gelen çevrim kenarıdır. Union-find bunu tek geçişte bulur: kenarları sırayla ekleyin ve uçları zaten bağlantılı olan ilk kenar yanıtı verir.
Her bir kenarı, önce sondakini kaldırmayı deneyin
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir kenarı kaldır ve diğer n-1 kenarın bir ağaç oluşturup oluşturmadığını kontrol et. n düğüm ve n-1 kenarla, bu ancak 1. düğümden başlayan bir arama n düğümün tamamına ulaştığında gerçekleşir. Kenarları listenin sonundan başlayarak dene; böylece başarılı olan ilk kaldırma, en sondaki kenarı verir. Her kenarın indeksini komşuluk listelerinde sakla; böylece arama, hiçbir şeyi yeniden oluşturmadan kaldırılan kenarı atlayabilir.
Her deneme O(n) süren tam bir aramadır ve n deneme yapılabilir: n = 5000 olduğunda en fazla 2.5 × 10^7 adım.
Algoritma
- Her komşu için ona giden kenarın indeksini tutan komşuluk listeleri oluşturun.
- Son indeksten 0'a kadar
skipiçin, 1 numaralı düğümden başlayarak arayın veskipindeksine sahip kenarı yok sayın. - Aramanın ulaştığı düğümleri sayın.
- Tüm
ndüğümlere ulaşırsaedges[skip]değerini döndürün.
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 []Yaprakları soyun
Sezgi
Tek kenarı olan bir düğüm, yani yaprak, bir döngü üzerinde olamaz; çünkü bir döngü, düğümlerinin her birine girer ve oradan çıkar. Bir yaprağı kaldırmak komşusunu yaprağa dönüştürebilir; bu yüzden hiç yaprak kalmayana kadar yaprakları soymaya devam et. Geriye tam olarak döngü kalır, çünkü döngüdeki her düğüm iki döngü kenarını korur. İkinci örnekte 5 numaralı düğüm soyulur, 1 numaralı düğüm iki kenarını korur ve 1 ile 4 arasındaki düğümler kalır.
Kalan iki düğüm arasındaki her kenar bir döngü kenarıdır; çünkü döngü düğümleri arasındaki ikinci bir bağlantı ikinci bir döngü oluştururdu. Bu yüzden edges öğelerini sondan başlayarak tara ve uçlarının ikisi de kalan ilk kenarı döndür.
Algoritma
- Bitişiklik listelerini oluştur ve her düğümün derecesini say.
- Derecesi 1 olan her düğümü bir yığına ekle.
- Bir yaprağı yığından çıkar, derecesini 0 olarak ayarla ve kalan komşusunun derecesini azalt; derecesi 1'e düştüğünde bu komşuyu yığına ekle.
- Yığın boşaldığında, derecesi 0'dan büyük olan düğümler çevrimi oluşturur.
edgesdizisini sondan tara ve uçlarının ikisi de kalan ilk kenarı döndür.
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 []Birleşim-bulma: döngüyü kapatan ilk kenar
Sezgi
Kenarları listedeki sırayla ekleyin ve hangi düğümlerin birbirine bağlı olduğunu takip edin. Döngü kapanana kadar her kenar, aralarında bir yol bulunmayan iki parçayı birleştirir. Uçları zaten bağlı olan ilk kenar döngüyü kapatır. Döngünün diğer kenarları bundan önce eklendiği için, döngüde en son görünen kenar budur. İkinci örnekte [1, 4], 1 ve 4 düğümlerinin zaten birleştirilmiş olduğunu bulur ve [1, 5] hiçbir zaman okunmaz.
Union-find tek bir dizi tutar: parent; bir düğümden işaretçileri takip etmek, parçanın kökünde sonlanır. Küçük parçayı büyük parçanın altına eklemek ve find sırasında düğümleri büyükanne ve büyükbabalarına yönlendirmek, zincirleri kısa tutar. Böylece her işlem amortize O(α(n)) maliyetlidir; burada α, ters Ackermann fonksiyonu, gerçek girdiler için en fazla 4'tür.
Algoritma
- 1'den
n'e kadar her düğümü kendisini gösterecek şekilde ayarla:parent[x] = xve boyutunu 1 yap. edgesüzerinde sırayla ilerle.[u, v]içinu'nun kökünü vev'nin kökünü bul.- Kökler eşleşiyorsa,
[u, v]döngüyü kapatır: olduğu gibi döndür. - Eşleşmiyorsa, büyük küme küçük olanı içine alır: büyük kümenin kökü, küçük kümenin kökünün ebeveyni olur ve boyutlar toplanır.
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 []
Tuzaklar ve uç durumlar
- Listenin son kenarını döndürmek. İkinci örnekte bu
[1, 5]olur ve bunu kaldırmak 5 numaralı düğümün bağlantısını keser. - Katmanları kaldırdıktan sonra baştan taramak. Bu, ikinci örnekte
[1, 2]olan en erken döngü kenarını döndürür. - Çifti sıralamak veya ters çevirmek. Liste
[3, 1]içeriyorsa,[1, 3]değil,[3, 1]döndürün. - 0'dan
n-1'e kadar olan düğümler için dizileri boyutlandırmak. Düğümler 1'den başlayarak numaralandırılır, bu nedenlennumaralı düğüm içinn+1yuvalı bir dizi gerekir. - Döngü boyunca özyinelemeli ilerlemek. Tüm 5000 düğümden geçebilir; bu, Python'ın varsayılan özyineleme sınırının beş katıdır. Bu nedenle
findiçinde açık bir yığın ve döngü kullanın.
Sıkça sorulan sorular3
Redundant Connection'ın zaman karmaşıklığı nedir?
Union-find, n kenarın üzerinden tek geçişte çözer: O(n · α(n)) zaman; burada α(n), pratikte en fazla 4'tür ve O(n) alan kullanır. Yaprakları ayıklamak da O(n) zaman alır. Her silme işlemini yeni bir aramayla denemek O(n²) maliyetlidir.
Bir ağaç bırakmak için hangi kenarlar kaldırılabilir?
Tam olarak çevrim üzerindeki kenarlar. Her birinin uçları arasında çevrimin geri kalanından geçen ikinci bir yol vardır; bu nedenle onu kaldırmak grafiğin bağlantılı kalmasını sağlar. Diğer tüm kenarlar grafiğin iki parçası arasındaki tek bağlantıdır ve kaldırıldıklarında bu parçaları ayırırlar.
Tekrarlı Bağlantı DFS ile çözülebilir mi?
Evet. Her bir kenarı eklemeden önce, eklenmiş kenarları kullanarak bir uçtan başlayıp arama yap; diğer ucuna zaten ulaşılabilen ilk kenar yanıttır. Bu, her kenar için O(n), toplamda O(n²) maliyetlidir; union-find ise aynı soruyu sabite yakın sürede yanıtlar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def findRedundantConnection(edges):
# Kodu buraya yazınTest #1
Test #2
Argüman
edges = [[1, 2], [1, 3], [2, 3]]
Beklenen Çıktı
[2, 3]