A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two operations :
- Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
- Union: Join two subsets into a single subset.
Space Complexity: O(N) for N elements
Time Complexity: O(N + M lg*N) for N elements and M queries, where lg* is the inverse of Ackermann’s function. For all practical applications, lg*N <= 5
For a complete tutorial on disjoint set data structure, view the topcoder tutorial.
For an application of union find data structure, view Kruskal’s MST algorithm.
Take a look at the C++ implementation.