İçeriğe geç

Erişilebilir çift kontrolü

Kolay#union-find#connectivity~15 dk

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

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

Kısıtlar

  • nodes are numbered 0 to n − 1

Kodda değil de fikirde mi takıldın? Disjoint set temelleri bunu anlatıyor.

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