* union find data structure for javascript * * In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, * is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition * of a set into dis
(n, key)
| 15 | * you can learn more on disjoint-set / union–find data structure at https://en.wikipedia.org/wiki/Disjoint-set_data_structure |
| 16 | */ |
| 17 | function UnionFind(n, key) { |
| 18 | if (!(this instanceof UnionFind)) return new UnionFind(n) |
| 19 | if (key && typeof key !== 'function') { |
| 20 | throw new Error('key has to be a function or else left undefined') |
| 21 | } |
| 22 | let cnt, length |
| 23 | // init Union Find with number of distinct groups. Each group will be referred to as index of the array of size 'size' starting at 0. |
| 24 | // Provide an optional key function that maps these indices. I.e., for the groups starting with 1 provide function(a){return a-1;}. The default value is function(a){return a;}. |
| 25 | key = |
| 26 | key || |
| 27 | function (a) { |
| 28 | return a |
| 29 | } |
| 30 | cnt = length = n |
| 31 | const id = new Array(n) |
| 32 | const sz = new Array(n) |
| 33 | for (let i = 0; i < n; i++) { |
| 34 | id[i] = i |
| 35 | sz[i] = 1 |
| 36 | } |
| 37 | // Returns the number of elements of uf object. |
| 38 | this.size = function () { |
| 39 | return length |
| 40 | } |
| 41 | // Returns the number of distinct groups left inside the object. |
| 42 | this.count = function () { |
| 43 | return cnt |
| 44 | } |
| 45 | // Return the root (value) of the group in which p is. |
| 46 | this.find = function (p) { |
| 47 | p = key(p) |
| 48 | while (p !== id[p]) { |
| 49 | id[p] = id[id[p]] |
| 50 | p = id[p] |
| 51 | } |
| 52 | return p |
| 53 | } |
| 54 | // Returns true if p and p are both in same group, false otherwise. |
| 55 | this.connected = function (p, q) { |
| 56 | p = key(p) |
| 57 | q = key(q) |
| 58 | ensureIndexWithinBounds(p, q) |
| 59 | return this.find(p) === this.find(q) |
| 60 | } |
| 61 | // Combine elements in groups p and q into a single group. In other words connect the two groups. |
| 62 | this.union = function (p, q) { |
| 63 | p = key(p) |
| 64 | q = key(q) |
| 65 | ensureIndexWithinBounds(p, q) |
| 66 | const i = this.find(p) |
| 67 | const j = this.find(q) |
| 68 | if (i === j) return |
| 69 | if (sz[i] < sz[j]) { |
| 70 | id[i] = j |
| 71 | sz[j] += sz[i] |
| 72 | } else { |
| 73 | id[j] = i |
| 74 | sz[i] += sz[j] |
nothing calls this directly
no test coverage detected