Snippet from https://play.nim-lang.org

playground.nim

## Union-Find Data Type API
##
##
## **Goal:** 
## - Design efficient data structure for union-find
## - Number of objects N can be huge
## - Number of operations M can be huge
##
## **type UFobj:**
##     - newUFobj(N: int) => initialize union-find data structure with N objects [0, N)
##     - proc union*(p, q: int) => add connection between p and q
##     - proc connected(p, q: int): connected => are p and q in the same component?
##     - proc find(p: q) => component identifier for p [0, N)
##     - proc count() => number of components

type 
  UFobj* = object
    ## **Union-Find data structure**
    ##
    ## It has two sequence of `int`s, for storing the value tree, **id** and size of each tree, **sz**.
    ## id[i] = id[...id[i]...]
    id, sz: seq[int]
  UFref* = ref UFobj
  UFStruct* = UFobj | UFref

template makeUF(n: int): untyped =
  result.id = newSeq[int](n)
  result.sz = newSeq[int](n)
  for i in 0 .. n - 1:
    result.id[i] = i
    result.sz[i] = 1

proc newUFobj*(n: int): UFobj =
  ## **Worst case: O(n)**
  ##
  ## Creates a new Union Find data structure of `int` in the stack. The values are in the heap since
  ## they're in a `seq[int]`
  makeUF(n)

proc newUFref*(n: int): UFref =
  ## **Worst case: O(n)**
  ##
  ## Creates a new Union Find data structure of `int` in the heap. The values are in the heap since
  ## they're in a `seq[int]`. Generally, newUFobj is more desirable
  makeUF(n)

proc root(structure: UFStruct; n: int) = 
  ## **Worst ase: O(n)**
  ##
  ## Finds the root of a value in a component.
  var result = n
  while structure.id[result] != result:
    result = structure.id[result]