Resources:
- An article on Path Compression and Union By Rank. Somewhat technical, specifically in time/space analysis: people.cs.georgetown.edu/jtha...
- A GeeksForGeeks article on Path Compression and Union By Rank. Has actual implementations in a variety of languages: www.geeksforgeeks.org/union-b...
Notes:
- A major "issue" of the union find is that even though you can easily merge 2 subsets, you cannot (easily) split them. If whatever problem you're dealing with requires splitting components after they've been created, and there's no way to re-format the problem such that the splitting can be avoided, the union find most likely isn't the data structure you want to go with.
- Another equally valid way to implement representative elements is to make it such that their parent is set to some sentinel value (ex: -1, INT_MAX, etc) rather than set to itself.
- You can easily implement the union find without creating a struct/class for it. Just declare the parent[] list, the union and find functions, and you're good to go. I used a class in the video because I think it's easiest to envision the union find as a self-contained structure rather than just a list and 2 functions, but at the end of the day, it doesn't really matter.
- The union by rank optimization requires allocating another array/list of the same size as the number of elements inside the union find, so there may be rare instances when this optimization causes problems (i.e. if the max number of elements is extremely large). Path compression doesn't utilize any additional space that isn't already allocated for the unoptimized find function, so that isn't a concern there.
Here's a problem I like for which the union find can be pretty much directly applied:
codeforces.com/contest/1167/p...