Disjoint Set Algorithm

The Disjoint Set Test Algorithm, also known as Union-Find or Merge-Find, is a data structure and algorithm that deals with maintaining a collection of disjoint sets, where each set represents a group of elements. The primary operations supported by this data structure are union, find, and sometimes, make-set. Union combines two disjoint sets into a single set, find determines the representative element of a set that an item belongs to, and make-set creates a new set containing a single element. The algorithm is particularly useful in applications like network connectivity, image processing, and Kruskal's Minimum Spanning Tree algorithm for graphs. The key feature of the Disjoint Set Test Algorithm is its ability to efficiently determine if two elements belong to the same set or not, as well as perform set unions with a minimal amount of work. To achieve these goals, the algorithm uses a tree-like data structure where each node has a parent pointer. The root node of each tree represents the representative element of the set. When performing a find operation, the algorithm follows the parent pointers until it reaches the root node, which is the representative element. To improve efficiency, the algorithm uses path compression, which flattens the tree structure by making each node point directly to the root during the find operation. For the union operation, the algorithm performs a weighted union by rank, where the tree with the smaller rank is attached to the tree with the larger rank, resulting in more balanced trees and faster subsequent operations.
/*
 * Copyright (c) 2017 Kotlin Algorithm Club
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

package com.algorithmexamples.datastructures

class DisjointSet(val size: Int) {
    private val parent = IntArray(size)
    private val rank = ByteArray(size)
    public var count = size
        private set

    init {
        for (i in parent.indices) {
            parent[i] = i
        }
    }

    public fun connected(v: Int, w: Int): Boolean {
        return find(v) == find(w)
    }

    public fun find(v: Int): Int {
        var v = v
        while (parent[v] != v) {
            parent[v] = parent[parent[v]]
            v = parent[v]
        }
        return v
    }

    public fun union(v: Int, w: Int) {
        val rootV = find(v)
        val rootW = find(w)
        if (rootV == rootW) return
        if (rank[rootV] > rank[rootW]) {
            parent[rootW] = rootV
        } else if (rank[rootW] > rank[rootV]) {
            parent[rootV] = rootW
        } else {
            parent[rootV] = rootW
            rank[rootW]++
        }
        count--
    }
}

LANGUAGE:

DARK MODE: