Erişilebilir çift kontrolü
Görev tanımı
Problem
Bir ağın 0'dan n eksi 1'e kadar numaralanmış n düğümü ve düğüm çiftleri arasında iki yönlü bağlantılardan oluşan bir listesi var. Bir kaynak düğüm ve bir hedef düğüm verildiğinde, birinden diğerine giden bir bağlantı zinciri olup olmadığına karar ver. Bir düğüm her zaman kendisine ulaşır.
Örnekler
Input: n = 3, links = [[0, 1], [1, 2], [2, 0]], source = 0, target = 2
Output: True
Input: n = 6, links = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source = 0, target = 5
Output: False
Neden: bağlantılar iki ayrı grup oluşturuyor, {0, 1, 2} ve {3, 4, 5}
Input: n = 1, links = [], source = 0, target = 0
Output: True
Neden: edge case: bir düğüm hiçbir bağlantı olmadan kendisine ulaşır
İpuçları
0 / 3
Tam rota önemli değil, yalnız iki düğümün aynı bağlı grupta olup olmadığı önemli.
Her düğümün kendi grubunda olduğu bir durumla başla. Her bağlantı sana iki grubun aslında bir olduğunu söyler.
Her düğüme kendisini gösteren bir parent pointer'ı ver. Her bağlantı için parent pointer'larını izleyerek iki ucun kökünü bul ve bir kökü diğerine göster. Sonunda cevap, kaynak ile hedefin aynı köke sahip olup olmadığı.
- Hedef zaman
- O((n + m) · α(n))
- Hedef alan
- O(n)
Kısıtlar
- nodes are numbered 0 to n − 1
Çözüm
Her bağlantı iki ucunun gruplarını birleştirir; bu yüzden her bağlantı işlendikten sonra ayrık kümeler, bağlantılar hangi sırayla gelirse gelsin tam olarak bağlı gruplardır. Erişilebilirlik o zaman köklerin tek bir karşılaştırmasıdır. Bir find sırasında ziyaret edilen her düğümü büyük ebeveynine gösteren path halving, hiçbir ek kayıt tutmadan parent zincirlerini kısa tutar. m bağlantıyla zaman O((n + m) × ters Ackermann fonksiyonu), pratikte doğrusal; alan O(n).
def reachable(n, links, source, target):
parent = list(range(n)) # every node starts alone
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for u, v in links:
parent[find(u)] = find(v) # a link merges two groups
return find(source) == find(target)
print(reachable(3, [[0, 1], [1, 2], [2, 0]], 0, 2)) # -> True
print(reachable(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5)) # -> False
print(reachable(1, [], 0, 0)) # -> TrueKodda değil de fikirde mi takıldın? Disjoint set temelleri bunu anlatıyor.