#5.8. Data Structures for Disjoint Sets

• ref
• Partition
  • A partition of a set $X$ is a set of non-empty subsets of $X$ such that every element x in $X$ is in exactly one of these subsets.
  • Example: $X=\{1,2,3,4,5,6\}\to \{\{1,3,5\},\{2\},\{4,6\}\}$
• Disjoint-set data structure (union-find data structure)
  • Used to effectively manage a collection of subsets that partition a given set of elements.
• Basic operations on disjoint sets
  • Makeset(x)
    • Make a set containing only the given element x.
  • S = Find(x)
    • Determine which set the particular element x is in.
      • Typically return an element that serves as the subset’s representative.
      • May be used to determine if two elements are in the same subset.
  • Union(x, y) (or Merge(x, y))
    • Merge two subsets into a single subset.
• Applications
  • Tracking the connected components of an undirected graph
    • Decide if two vertices belong to the same component, or if adding an edge between them would result in a cycle.
    • Useful for implementing the Kruskal’s algorithm for finding minimum spanning tree
• Scheduling with deadlines
• Computing shorelines of a terrain
• Classifying a set of atoms into molecules or fragments.
• Connected component labeling in image analysis
• Example
  • $U=\{a,b,c,d,e\}$
  • For (each $x$ $\in$ $U$)
    • Makeset($x$); → {$a$}, {$b$}, {$c$}, {$d$}, {$e$}
    • Union($a$, $c$); → {$a$, $c$}, {$b$}, {$d$}, {$e$}
    • {a, c} = Find(a);
    • Union($c$, $e$); → {$a$, $c$, $e$}, {$b$}, {$d$}
• Implementation of disjoint sets using reversed trees
  • Makeset(x)
    Makeset(x){
    	parent(x) := x
    	rank(x) := 0
    }
    

    • Time complexity: $O(1)$
• Two ways of implementing the Union Operation
  • Time complexity: $O(n)$
  • Time complexity: $O(\log n)$
• Union by rank
  • Always attach the smaller tree to the root of the larger tree.
  • The rank increases by one only if two trees of the same rank are merged.
    • The rank of a one-element tree is zero.
  • The Union and Find operations can be done in $O(\log n)$ in the worst case.
    • The number of elements in a tree of rank $r$ is at least $2^r$ (Proof by induction)
    • The maximum possible rank of a tree with n elements is $O(\log n)$.

Disjoint set의 path compression 연산에 대해서도 알아볼 것.

• S = Find(x)
  • Time complexity: $O(depthofxinthetree)$
    Find(x) {
      if (x == parent(x))
        return x 
      else
        return Find(parent(x)) 
    }
    Find(x) {
      while (x != parent(x))
        x := parent(x)
      return x
    }
    

• Union(x, y)
  • Time complexity: 2 Find op’s + $O(1)$
    Union(x, y) { 
      x0 := Find(x) 
      y0 := Find(y) 
      if (x0 == y0)
        return
      if (rank(x0) > rank(y0))
        parent(y0) := x0
      else
        parent(x0) := y0
      if (rank(x0) == rank(y0))
        rank(y0) := rank(y0)+1
    }
    

• Method
  • $d_{max}$ : the maximum of the deadlines for $n$ jobs.
  • Add a job as late as possible to the schedule being built, but no later than its deadline.
  • Sort the jobs in non-increasing order by profit.
  • Initialize $d_{max}+1$ disjoint sets, containing the integers $0,1,2,...,d_{max}$
  • For each job in the sorted order,
    • Find the set $S$ containing the minimum of its deadline and $n$.
      • If $small(S)=0$, reject the job.
      • Otherwise, schedule it at time $small(S)$, and merge $S$ with the set containing $small(S)-1$.
• Time complexity
  • $O(n\log m)$ for the disjoint set manipulation, where $m$ is the minimum of $n$ and $d_{max}$
  • $O(n\log n)$ for sorting the profits.
• Example