如何使用并查集解决朋友圈问题？

// 数组实现适合元素个数固定的场景
class UnionFind(n: Int) {
    // 创建一个长度为 n 的数组，每个位置上的值初始化数组下标，表示初始化时有 n 个子集
    private val parent = IntArray(n) { it }
    ...
}

// 散列表实现适合元素个数不固定的场景
class UnionFind() {
    // 创建一个空散列表，
    private val parent = HashMap<Int, Int>()

    // 查询操作
    fun find(x: Int): Int {
        // 1. parent[x] 为 null 表示首次查询，先加入散列表中并指向自身
        if (null == parent[x]) {
            parent[x] = x
            return x
        }
        // 下文说明查询操作细节...
    }
}

class UnionFind(n: Int) {

    // 创建一个长度为 n 的数组，每个位置上的值初始化数组下标，表示初始化时有 n 个子集
    val parent = IntArray(n) { it }

    // 查询操作（遍历写法）
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            key = parent[key]
        }
        return key
    }

    // 合并操作
    fun union(x: Int, y: Int) {
        // 1. 分别找出两个元素的根节点
        val rootX = find(x)
        val rootY = find(y)
        // 2. 任意选择其中一个根节点成为另一个根节点的子树
        parent[rootY] = rootX
    }

    // 判断连通性
    fun isConnected(x: Int, y: Int): Boolean {
        // 判断根节点是否相同
        return find(x) == find(y)
    }

    // 查询操作（递归写法）
    fun find(x: Int): Int {
        var key = x
        if (key != parent[key]) {
            return find(parent[key])
        }
        return key
    }
}

class UnionFind(n: Int) {

    private val parent = IntArray(n) { it }

    // 连通分量计数，初始值为元素个数 n
    var count = n

    // 合并操作
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if(rootX == rootY){
            // 未发生合并，则不需要减一
            return
        }
        // 合并后，连通分量减一
        parent[rootY] = rootX
        count --
    }
    ...
}

// 未优化版本
class Solution {
    fun equationsPossible(equations: Array<String>): Boolean {
        // 26 个小写字母的并查集
        val unionFind = UnionFind(26)

        // 合并所有等式
        for (equation in equations.filter { it[1] == '=' }) {
            unionFind.union(equation.first(), equation.second())
        }
        // 检查不等式是否与连通性冲突
        for (equation in equations.filter { it[1] == '!' }) {
            if (unionFind.isConnected(equation.first(), equation.second())) {
                return false
            }
        }
        return true
    }

    private fun String.first(): Int {
        return this[0].toInt() - 97
    }

    private fun String.second(): Int {
        return this[3].toInt() - 97
    }

    private class UnionFind() {
        // 代码略
    }
}

// 遍历写法
fun find(x: Int): Int {
    var key = x
    while (key != parent[key]) {
        parent[key] = parent[parent[key]] 
        key = parent[key]
    }
    return key
}

// 递归写法
fun find(x: Int): Int {
    var key = x
    if (key != parent[key]) {
        parent[key] = find(parent[key])
        return parent[key]
    }
    return key
}

private class UnionFind(n: Int) {
    // 父节点
    private val parent = IntArray(n) { it }

    // 节点的高度
    private val rank = IntArray(n) { 1 }

    // 连通分量
    var count = n
        private set

    // 查询（路径压缩）
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            parent[key] = parent[parent[key]]
            key = parent[key]
        }
        return key
    }

    // 合并（按秩合并）
    fun union(key1: Int, key2: Int) {
        val root1 = find(key1)
        val root2 = find(key2)

        if (root1 == root2) {
            return
        }
        if (rank[root1] > rank[root2]) {
            // root1 的高度更大，让 root2 成为子树，树的高度不变
            parent[root2] = root1
        } else if (rank[root2] > rank[root1]) {
            // root2 的高度更大，让 root1 成为子树，树的高度不变
            parent[root1] = root2
        } else {
            // 高度相同，谁当子树都一样
            parent[root1] = root2
            // root2 的高度加一
            rank[root2]++
            //  或
            //  parent[root2] = root1
            //  rank[root1] ++
        }
        count--
    }
}

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {

        // 位置
        fun position(row: Int, column: Int) = row * grid[0].size + column

        // 并查集
        val unionFind = UnionFind(grid)

        // 偏移量数组（向右和向下）
        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0))

        // 边界检查
        fun checkBound(row: Int, column: Int): Boolean {
            return (row in grid.indices) and (column in grid[0].indices)
        }

        for (row in grid.indices) {
            for (column in grid[0].indices) {
                if ('1' == grid[row][column]) {
                    // 消费（避免后续的遍历中重复搜索）
                    grid[row][column] = '0'
                    for (direction in directions) {
                        val newRow = row + direction[0]
                        val newColumn = column + direction[1]
                        if (checkBound(newRow, newColumn) && '1' == grid[newRow][newColumn]) {
                            unionFind.union(position(newRow, newColumn), position(row, column))
                        }
                    }
                }
            }
        }
        return unionFind.count
    }

    private class UnionFind(grid: Array<CharArray>) {

        // 父节点
        private val parent = IntArray(grid.size * grid[0].size) { it }

        // 节点高度
        private val rank = IntArray(grid.size * grid[0].size) { 1 }

        // 连通分量（取格子 1 的总数）
        var count = grid.let {
            var countOf1 = 0
            for (row in grid.indices) {
                for (column in grid[0].indices) {
                    if ('1' == grid[row][column]) countOf1++
                }
            }
            countOf1
        }
            private set

        // 合并（按秩合并）
        fun union(key1: Int, key2: Int) {
            val root1 = find(key1)
            val root2 = find(key2)
            if (root1 == root2) {
                // 未发生合并，则不需要减一
                return
            }
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1
            } else if (rank[root2] > rank[root1]) {
                parent[root1] = root2
            } else {
                parent[root1] = root2
                rank[root2]++
            }
            // 合并后，连通分量减一
            count--
        }

        // 查询（使用路径压缩）
        fun find(x: Int): Int {
            var key = x
            while (key != parent[key]) {
                parent[key] = parent[parent[key]]
                key = parent[key]
            }
            return key
        }
    }
}