Union Find

Find: Determine which subset a particular element is in. Used to determine if two elements are in the same subset.

Union: Join two subsets into the same subset.

Algorithm Procedure:

• Initially, all subsets only contains one elements,
  assign its id to the element's id; Therefore, currently we have id[0] = 0, id[1] = 1, id[2] = 2;

• Process each edges one by one:

  Edge 0-1: Since they're in different subsets: find(0) != find(1), we perform union operation on them by make node 0 as node 1's parent or vice-versa; Now we have id[0] = 1, id[1] = 1, id[2] = 2;

  Edge 1-2: We also need to take union of these two subsets, now we have id[0] = 2, id[1] = 2, id[2] = 2;

Time Complexity: Since for every union, we need to update all elements in a subset, the time complexity is O(n^2)

Union By Rank: