Алгоритми та структури даних · Middle · Запитання 34 з 75
Що підтримує структура union-find (система неперетинних множин)?
- ✓Правильна відповідь: Об'єднання множин і перевірку, чи два елементи в одній множині
- 2Сортування елементів і пошук k-го найменшого
- 3Зберігання пар ключ-значення зі швидкими запитами діапазонів
Пояснення
union(a, b) зливає дві групи, а find(a) повертає представника групи. Зі стисненням шляхів і об'єднанням за рангом обидві операції майже O(1). Типові застосування: компоненти зв'язності, MST Крускала, «чи це акаунти однієї людини?»