Union-Find sets 簡易操作範例

ufs.coffee

'use strict'

class UFS

  constructor: (count) ->
    @_father = []
    @_rank = []

    @_initSet = (count) ->
      for i in [0..count-1]
          @_father[i] = i
          @_rank[i] = 0
          console.log i
      return

    @_initSet count

  makeSet: () ->
    n = @_father.length
    @_father[n] = n
    @_rank[n] = 0

    return n

  findSet: (x) ->
    if (x != @_father[x])
      @_father[x] = @findSet(@_father[x])

    return @_father[x]

  union: (x, y) ->
    x = @findSet(x)
    y = @findSet(y)

    if (@_rank[x] > @_rank[y])
      @_father[y] = x
    else
      if (@_rank[x] == @_rank[y])
        @_rank[y] += 1
      @_father[x] = y

ufs = new UFS(8)

ufs.union(0,1)
ufs.union(1,2)
ufs.union(2,3)
ufs.union(5,6)
ufs.union(7,1)

console.log ufs._father
console.log ufs._rank