@algorithm.ts/findset NPM

A typescript implementation of the Findset data structure, usually also known as Disjoint-set data structure.

The find-set is a data structure used to maintain the node relationship in a forest. Find set support to perform the following operations under the amortized constant time complexity:

Determine whether two nodes are in a synonymous tree.
Merge two trees.

Install

npm

npm install --save @algorithm.ts/findset

yarn
```
yarn add @algorithm.ts/findset
```

Usage

Create a ordinary findset:

import { Findset } from '@algorithm.ts/findset'

const findset = new Findset()

// Initialize the findset with 1000 node.
findset.init(1000)

// Find the root node of the tree where the given node located.
// !!!Attention. The node number must be a positive integer in range of [1, 1000]
findset.root(4)   // => 4

// Merge two trees.
findset.merge(2, 3)

assert(findset.root(2) === findset.root(3))

Create a heuristic findset:

The heuristic find-set maintains the number of nodes of each tree on the basis of the ordinary version. When merging trees, always use the root node of the tree with more nodes as the root node of the new tree, which can reduce the number of executions of subsequent queries.

import { HeuristicFindset } from '@algorithm.ts/findset'

const findset = new HeuristicFindset()

// Initialize the findset with 1000 node.
findset.init(1000)

// Find the root node of the tree where the given node located.
// !!!Attention. The node number must be a positive integer in range of [1, 1000]
findset.root(4)   // => 4

// Merge two trees.
findset.merge(2, 3)

assert(findset.root(2) === findset.root(3))

// Count the nodes of a tree.
findset.count(1)   // => 1
findset.count(2)   // => 2
findset.count(3)   // => 2
findset.count(4)   // => 1

Create an enhanced findset:

On the basis of ordinary findset, this enhanced version also supports to get all the nodes on a given tree (access through the root node).

import { EnhancedFindset } from '@algorithm.ts/findset'

const findset = new EnhancedFindset()

findset.init(100)
findset.count(1)      // => 1
findset.merge(1, 2)
findset.count(1)      // => 2
findset.count(2)      // => 2
findset.getSetOf(1)   // => Set {1, 2}
findset.getSetOf(2)   // => Set {1, 2}

Example

A solution for leetcode "Find All People With Secret" (https://leetcode.com/problems/find-all-people-with-secret/):

import { EnhancedFindset } from '@algorithm.ts/findset'

class MyFindset extends EnhancedFindset {
  public resetNode(x: number): void {
    this._parent[x] = 0
    this._sets[x].clear()
    this._sets[x].add(x)
  }
}

const MAX_N = 1e5 + 10
const answer: Set<number> = new Set()
const nodes: Set<number> = new Set()
const visited: Uint8Array = new Uint8Array(MAX_N)
const findset = new MyFindset()

export function findAllPeople(N: number, meetings: number[][], firstPerson: number): number[] {
  answer.clear()
  answer.add(1)
  answer.add(firstPerson + 1)

  const M: number = meetings.length
  meetings
    .sort((x, y) => x[2] - y[2])
    .forEach(item => {
      item[0] += 1
      item[1] += 1
    })

  findset.init(N)
  for (let i = 0, j: number; i < M; i = j) {
    const t: number = meetings[i][2]
    for (j = i + 1; j < M; ++j) {
      if (meetings[j][2] !== t) break
    }

    nodes.clear()
    for (let k = i; k < j; ++k) {
      const [x, y] = meetings[k]
      nodes.add(x)
      nodes.add(y)
    }

    for (const x of nodes) {
      findset.resetNode(x)
      visited[x] = 0
    }

    for (let k = i; k < j; ++k) {
      const [x, y] = meetings[k]
      findset.merge(x, y)
    }

    for (const x of nodes) {
      if (!answer.has(x)) continue

      const xx: number = findset.root(x)
      if (visited[xx]) continue
      visited[xx] = 1

      const xxSet = findset.getSetOf(xx)!
      for (const t of xxSet) answer.add(t)
    }
  }

  return Array.from(answer)
    .map(x => x - 1)
    .sort((x, y) => x - y)
}