LeetCode in Kotlin

3607. Power Grid Maintenance

Medium

You are given an integer c representing c power stations, each with a unique identifier id from 1 to c (1‑based indexing).

These stations are interconnected via n bidirectional cables, represented by a 2D array connections, where each element connections[i] = [ui, vi] indicates a connection between station ui and station vi. Stations that are directly or indirectly connected form a power grid.

Initially, all stations are online (operational).

You are also given a 2D array queries, where each query is one of the following two types:

Return an array of integers representing the results of each query of type [1, x] in the order they appear.

Note: The power grid preserves its structure; an offline (non‑operational) node remains part of its grid and taking it offline does not alter connectivity.

Example 1:

Input: c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

Output: [3,2,3]

Explanation:

Example 2:

Input: c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

Output: [1,-1]

Explanation:

Constraints:

Solution

import java.util.PriorityQueue

class Solution {
    private class UF(n: Int) {
        val par: IntArray = IntArray(n)
        val pq: Array<PriorityQueue<Int>> = Array(n) { PriorityQueue() }
        val active: BooleanArray = BooleanArray(n)

        init {
            for (i in 0 until n) {
                active[i] = true
                par[i] = i
                pq[i].add(i)
            }
        }

        fun find(u: Int): Int {
            if (par[u] == u) {
                return u
            }
            par[u] = find(par[u])
            return par[u]
        }

        fun union(u: Int, v: Int) {
            val pu = find(u)
            val pv = find(v)
            if (pu == pv) {
                return
            }
            if (pq[pu].size > pq[pv].size) {
                while (pq[pv].isNotEmpty()) {
                    pq[pu].add(pq[pv].poll())
                }
                par[pv] = pu // Should be pu, not par[pu]
            } else {
                while (pq[pu].isNotEmpty()) {
                    pq[pv].add(pq[pu].poll())
                }
                par[pu] = pv // Should be pv, not par[pv]
            }
        }

        fun inactive(u: Int) {
            active[u] = false
        }

        fun check(u: Int): Int {
            if (active[u]) {
                return u
            }
            val pu = find(u)
            while (pq[pu].isNotEmpty() && !active[pq[pu].peek()]) {
                pq[pu].poll()
            }
            return if (pq[pu].isNotEmpty()) pq[pu].peek() else -2
        }
    }

    fun processQueries(c: Int, connections: Array<IntArray>, queries: Array<IntArray>): IntArray {
        val uf = UF(c)
        for (con in connections) {
            val u = con[0]
            val v = con[1]
            uf.union(u - 1, v - 1)
        }
        val res = mutableListOf<Int>()
        for (q in queries) {
            if (q[0] == 1) {
                res.add(uf.check(q[1] - 1) + 1)
            } else {
                uf.inactive(q[1] - 1)
            }
        }
        return res.toIntArray()
    }
}