Disjoint set union(DSU) have a following operation over given elements: Add element to a set, combine any two sets, tell in which set a specific element is. As described in more detail later, the data structure allows you to do each of these operations in almost O(1) time on average.