Алгоритми та структури даних · Senior · Запитання 47 з 75
Чому union-find не знаходить цикли в орієнтованому графі?
- 1Він може зберігати лише вершини-числа
- 2Йому бракує пам'яті на орієнтованих графах
- ✓Правильна відповідь: Він ігнорує напрямок, тож «ромб» виглядає як цикл
Пояснення
Union-find відстежує зв'язність, а не напрямок. У DAG два шляхи до тієї самої вершини («ромб») з'єднали б уже зв'язані вершини, що схоже на цикл, але ним не є.