Disjoint Set Union (Advanced)
Learn Disjoint Set Union (Advanced) (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Disjoint Set Union: Size, Components and Rollback Union-Find keeps groups of elements and answers "are a and b in the same group?". Two optimisations make it almost O(1) per operation: union by size (hang the smaller tree under the larger) and path compression (point every node visited by find straight at the root). Together the cost is O(α(n)) , where α grows so slowly that it is at most 4 for any real input. Track the size of each group and the number of components for free.