Why it works
- An edge puts its two ends in one group, and joining two groups never splits anything, so after all edges a group is exactly a set of vertices that can reach each other.
- A group is named by its root. Two vertices are in one group when find gives them the same root, however many edges lie between them.
- The paths themselves are never built: the answer is one comparison of two roots.
Complexity
Time O(n + m · h) for m edges, where h is the height of the trees: up to n with this plain find, and almost a constant once find re-hangs the vertices it passes straight on the root and the smaller tree goes under the bigger one. Memory O(n) for parent.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗