İçeriğe geç

Kenarlar tek bir ağaç mı

Kolay#union-find#cycle-detection~15 dk

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

Hedef zaman
O(n · α(n))
Hedef alan
O(n)

Kısıtlar

  • nodes are labelled 0 to n − 1

Kodda değil de fikirde mi takıldın? Bileşenler ve döngüler bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case