Strongly Connected Components
Yönlü bir grafın n düğümü vardır; düğümler 0 ile n-1 arasında numaralandırılmıştır ve edges listesinde, [from, to] bir düğümden from düğümüne, to düğümüne giden bir kenarı belirtir.
Güçlü bağlı bileşen, kenarları izleyerek her düğümün diğer tüm düğümlere ulaşabildiği en büyük düğüm grubudur. Her düğüm tam olarak bir bileşene aittir ve hiçbir döngüde bulunmayan bir düğüm tek başına bir bileşen oluşturur. Güçlü bağlı bileşenlerin sayısını döndürün.
Fonksiyon
- ninteger
- düğüm sayısı
- edgesinteger-2d-array
- yönlü kenarlar, her biri [from, to] biçiminde
- Döndürürinteger
- kuvvetli bağlantılı bileşenlerin sayısı
Kısıtlar
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]olacak şekilde0 ≤ from, to < nvefrom ≠ to- Hiçbir kenar iki kez görünmez.
Örnekler
- Girdi
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Çıktı
- 3
- Açıklama
- 0, 1 ve 2 düğümleri bir döngü oluşturur, bu nedenle birbirlerine ulaşırlar. 3 ve 4 düğümleri birbirlerini gösterir. 5 düğümü 4'e ulaşır, ancak 5'e geri dönen hiçbir şey yoktur; bu yüzden tek başına kalır: 3 bileşen.
- Girdi
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Çıktı
- 4
- Açıklama
- 0 ve 1 düğümleri birbirini gösterir ve bir bileşen oluşturur. 2'den 3'e giden kenar yalnızca tek yöndedir, bu yüzden 2 ve 3 ayrıdır; 4 numaralı düğümün ise hiç kenarı yoktur: 4 bileşen.
Ek soru
Tüm grafiği tek bir güçlü bağlantılı bileşen hâline getirmek için en az kaç kenar eklemeniz gerekir?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İki düğüm, ancak her biri diğerine ulaşabiliyorsa aynı bileşeni paylaşır. Her düğümden yapılan bir arama bunu sınayabilir, ancak aynı kenarları tekrar tekrar dolaşır. Tek bir derinlik öncelikli arama, bir bileşenin nerede başladığı hakkında sana ne söyleyebilir?
Düğümleri, derinlik öncelikli aramanın onlara ilk ulaştığı sıraya göre numaralandır. Her düğüm için ayrıca
lowdeğerini izle: arama ağacında aşağı inip ardından, bileşeni hâlâ açık olan bir düğüme geri giden bir kenarı izleyerek ulaşabileceği en küçük numara.lowdeğeri kendi numarasına eşit olan bir düğüm, bileşeninin ilk düğümüdür.Ziyaret edilen düğümleri bir yığında tut. Bir düğümün
lowdeğeri kendi numarasına eşit olduğunda, yığından o düğüme kadar çıkar: bu düğümler bir bileşen oluşturur, dolayısıyla onu say. Testlerden biri aramayı 5000 düğüm derinliğine ulaştırıyor; bu yüzden özyineleme kullanmak yerine (düğüm, sonraki kenar) çerçevelerinden oluşan kendi yığınını tut.
Çözüm
Her bileşeni bir noktaya indirgeyin; bileşenler çevrimsiz bir grafik oluşturur. Kosaraju ve Tarjan algoritmaları, her bileşeni O(n + E) sürede bulmak için bundan yararlanır; burada E, kenar sayısıdır.
Her düğümden ileriye ve geriye doğru arama yap
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Düğümler u ve v, ancak ve ancak birbirlerine ulaşabiliyorlarsa aynı bileşeni paylaşır. Bu nedenle henüz bir bileşene dahil olmayan bir s düğümü için kenarlar boyunca ileriye, ters çevrilmiş kenarlar boyunca da geriye doğru arama yapın. Her iki aramada da bulunan düğümler, bu düğümün bileşenini oluşturur. İlk örnekte, 0'dan ileriye doğru yapılan aramada 0'dan 4'e kadar olan düğümler, geriye doğru yapılan aramada ise 0, 1 ve 2 bulunur; dolayısıyla {0, 1, 2} tek bir bileşendir.
Her bileşen, grafiğin büyük bölümünde iki arama gerektirir. 5001 düğümden geçen 5000 kenarlı bir zincirde her düğüm kendi başına bir bileşendir ve aramalar yaklaşık 2.5 × 10^7 düğümü ziyaret eder.
Algoritma
- Her düğümün giden ve gelen kenar listelerini oluşturun.
- Bileşeni olmayan sıradaki
sdüğümünü alın ve yeni bir bileşen sayın. s'nin giden kenarlar boyunca ulaştığı düğümleri ve gelen kenarlar boyuncas'ye ulaşan düğümleri işaretleyin.- Her iki aramada da işaretlenen her düğüm,
s'nin bileşenine katılır. Her düğüm bir bileşene sahip olduğunda sayıyı döndürün.
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 countKosaraju algoritması: iki geçiş
Sezgi
Bileşenler grafında bir bileşen, kendisinden çıkan hiçbir kenar olmayan bir yutaktır ve içinde başlatılan bir arama tam olarak o bileşeni bulur. Kosaraju algoritması, her aramanın bu şekilde davranmasını sağlayacak biçimde aramaları sıralar.
İlk geçiş, derinlik öncelikli araması tamamlandığında her düğümü listeler. İkinci geçiş, aynı bileşenlere sahip ters çevrilmiş grafı, tamamlanan son düğümden başlayarak arar. Bir kenar B bileşeninden C bileşenine gidiyorsa, B'nin son düğümü C'deki tüm düğümlerden sonra tamamlanır. Böylece ikinci geçiş C'ye ulaştığında, C'ye kenar gelen tüm bileşenler zaten atanmıştır ve ters çevrilmiş graf üzerinde arama C'den çıkamaz.
İlk örnekte düğümler şu sırayla tamamlanır: 4, 3, 2, 1, 0, 5. İkinci geçiş önce {5}, sonra {0, 1, 2}, ardından {3, 4} kümelerini toplar.
Algoritma
- Giden ve gelen kenar listelerini oluştur.
- Ziyaret edilmemiş her düğümden yinelemeli bir derinlik öncelikli arama başlat ve her düğüm tamamlandığında onu
orderlistesine ekle. orderlistesini sondan başlayarak dolaş. Bir bileşene ait olmayan her düğüm için yeni bir bileşen say ve o düğümden gelen kenarlar boyunca arama yaparak ulaştığı atanmamış her düğüme bu bileşeni ata. Sayıyı döndür.
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 countTarjan algoritması: low değerleriyle tek geçiş
Sezgi
Bir derinlik öncelikli arama çalıştır ve her düğüme ona ulaştığın sıraya göre bir numara ver: index. Bileşeni hâlâ açık olan ziyaret edilmiş düğümlerden oluşan bir yığın ve low değeri tut: bu, bir düğümün arama ağacında aşağı ilerleyip ardından yığındaki bir düğüme tek bir kenar üzerinden geri dönerek ulaşabildiği en küçük indekstir.
Bir düğüm, low değeri index değerinden küçükken tamamlanırsa, altındaki bir şey daha önce ziyaret edilmiş açık bir düğüme geri çıkıyor demektir; bu nedenle düğüm yığında kalır. Değerler eşitse, düğüm aramanın kendi bileşeninde ilk girdiği düğümdür: yığından o düğüme kadar çıkar ve bir bileşen say. Çıkarılmış bir düğüme giden kenar, geri ulaşamayan tamamlanmış bir bileşene çıkar; bu nedenle yok sayılır.
İlk örnekte, 3 düğümü {4, 3} kümesini, 0 düğümü ise {2, 1, 0} kümesini çıkarır. 5 düğümünün kenarı çıkarılmış 4 düğümüne gider; bu nedenle 5 tek başına çıkarılır.
Algoritma
- Ziyaret edilmemiş her düğüme sıradaki indeksi verin,
lowdeğerini aynı değere ayarlayın, düğüm yığınına ekleyin ve (düğüm, ilk kenar) çerçevesini yığına ekleyin. - Üst çerçevenin düğümünde incelenecek bir kenar varsa onu izleyin: ziyaret edilmemiş hedefe bir indeks ve çerçeve verilir; düğüm yığınındaki bir hedef ise
low[node]değerini kendi indeksine düşürür. - Aksi hâlde çerçeveyi çıkarın ve üst düğümün
lowdeğerinilow[node]değerine düşürün.low[node],index[node]değerine eşitse, düğüm yığınından düğüme kadar olan düğümleri çıkarın ve bir bileşen sayın.
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
Tuzaklar ve uç durumlar
- Kenar içermeyen düğümleri unutmak. İkinci örnekte 4 numaralı düğüm hiçbir kenarda yer almaz ve yine de bir bileşendir.
lowdeğerini yalnızca yığındaki düğümler yerine ziyaret edilmiş herhangi bir düğüm üzerinden düşürmek. İlk örnekte5 → 4kenarı, 5'in bileşenini kapatmasını engeller.- Kenarları çift yönlü kabul etmek. Bu, bağlı bileşenleri sayar: ilk örnekte 3 yerine 1 elde edilir.
- Python'da özyineleme kullanmak. 5000 düğümden geçen bir döngü, varsayılan 1000 sınırının beş katı olan 5000 çağrıyı iç içe yerleştirir. Kendi çerçeve yığınınızı tutun.
- Kosaraju'nun ikinci geçişini özgün kenarlar üzerinde ya da düğümlerin ilk ziyaret edilme sırasına göre çalıştırmak. Her iki yöntem de yalnızca tek yönde birbirine ulaşabilen bileşenleri birleştirir.
Sıkça sorulan sorular3
Kuvvetli bağlı bileşenleri bulmanın zaman karmaşıklığı nedir?
Kosaraju veya Tarjan algoritmasıyla O(n + E) zaman; çünkü her düğüm ve kenar sabit sayıda kez işlenir. Her ikisi de kenar listeleri ve arama yığınları için O(n + E) alan kullanır.
Kosaraju'nun algoritmasını mı yoksa Tarjan'ın algoritmasını mı kullanmalısınız?
Kosaraju algoritması iki basit aramadan oluşur ve hata yapması daha zordur. Tarjan algoritması ise low takibi karşılığında tek bir arama gerektirir ve ters çevrilmiş bir graf gerektirmez.
Güçlü bağlı bileşenler ile bağlı bileşenler arasındaki fark nedir?
Bağlantılı bileşenler kenar yönünü dikkate almaz: herhangi bir yol iki düğümü birleştirdiğinde bu düğümler birlikte kabul edilir. Güçlü bağlantılı bileşenlerde ise her düğümün diğerine ulaşabilmesi gerekir. İlk örnek bir bağlantılı bileşen, ancak üç güçlü bağlantılı bileşen içerir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def countSCC(n, edges):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Beklenen Çıktı
3