Kenarlar tek bir ağaç mı
Görev tanımı
Problem
Sana 0'dan n - 1'e kadar etiketlenmiş n düğüm ve yönsüz kenarlardan oluşan bir liste veriliyor. Kenarların tam olarak bir ağaç oluşturup oluşturmadığını döndür: her düğüm diğer her düğüme bağlı ve hiç döngü yok.
Örnekler
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: True
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: False
Neden: 1, 2 ve 3 bir döngü oluşturuyor
Input: n = 4, edges = [[0, 1], [2, 3]]
Output: False
Neden: edge case: döngü yok ama graf iki parça
İpuçları
0 / 3
n düğüm üzerinde bir ağacın tam olarak n - 1 kenarı vardır. Bu sayı tek başına birçok girdiyi dışarıda bırakır.
Tam olarak n - 1 kenarla bir graf tam olarak döngüsü olmadığında bir ağaçtır, çünkü o kadar kenarlı döngüsüz bir graf kendiliğinden bağlıdır.
Önce kenar sayısını kontrol et. Sonra her kenarın iki ucunu bir disjoint set'te birleştir; iki uç zaten bir kökü paylaşıyorsa o kenar bir döngüyü kapatır, yani cevap False.
- Hedef zaman
- O(n · α(n))
- Hedef alan
- O(n)
Kısıtlar
- nodes are labelled 0 to n − 1
Çözüm
Ağaçlarla ilgili iki gerçek bütün işi yapar. n düğüm üzerinde bir ağacın tam olarak n - 1 kenarı vardır ve n - 1 kenarlı, döngüsüz bir graf her zaman bağlıdır, çünkü iki farklı bileşeni birleştiren her kenar bileşen sayısını n'den tam olarak 1'e kadar bir azaltır. Yani sayı kontrolünden sonra tek soru bir kenarın bir döngüyü kapatıp kapatmadığıdır; bir disjoint set'in cevapladığı da tam olarak bu: iki ucunun kökü zaten aynı olan bir kenar önceden bağlı olan düğümleri bağlar. Path halving ağaçları sığ tutar. Zaman O(n · α(n)), pratikte doğrusal; alan O(n).
def is_single_tree(n, edges):
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb: # already connected: this edge closes a cycle
return False
parent[ra] = rb
return True
print(is_single_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])) # -> True
print(is_single_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) # -> False
print(is_single_tree(4, [[0, 1], [2, 3]])) # -> FalseKodda değil de fikirde mi takıldın? Bileşenler ve döngüler bunu anlatıyor.