Algorithms and Data Structures · Senior · Question 47 of 75
Why can't union-find detect cycles in a directed graph?
- 1It can only store vertices that are numbers
- 2It runs out of memory on directed graphs
- ✓Correct answer: It ignores direction, so a diamond looks like a cycle
Explanation
Union-find tracks connectivity, not direction. In a DAG two paths to the same vertex (a diamond) would join already connected vertices, which looks like a cycle but isn't one.