Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Union-Find

Disjoint-set forest with path compression and union by rank, demoing the p/moul/x/daily/disjointset library.

Merges applied

  • Union(0, 1)
  • Union(2, 3)
  • Union(1, 3)
  • Union(5, 6)
  • Union(7, 8)
  • Union(8, 9)

Partition of [0, 10)

4 groups:

  • {0, 1, 2, 3}
  • {4}
  • {5, 6}
  • {7, 8, 9}

Groups come out sorted, ordered by their smallest member, so the partition is identical whatever order the merges arrive in.