Class UnionFind

kotlin/Graphs/ConnectTheDots.kt:1–30

class UnionFind(size: Int) {
    private val parent = IntArray(size) { it }
    private val size = IntArray(size) { 1 }

    fun union(x: Int, y: Int): Boolean {
        var repX = find(x)
        var repY = find(y)
        if (repX != repY) {
            if (size[repX] > size[repY]) {
                parent[repY] = repX
                size[repX] += size[repY]
            } else {
                parent[repX] = repY
                size[repY] += size[repX]
            }
            // Return true if both groups were merged.
            return true
        }
        // Return false if the points belong to the same group.
        return false
    }

    fun find(x: Int): Int {
        if (x == parent[x]) {
            return x
        }
        parent[x] = find(parent[x])
        return parent[x]
    }
}

fun connectTheDots(points: List<List<Int>>): Int {
    val n = points.size