3607. Power Grid Maintenance

Leetcode link

题目简介

/**
 * @param {number} c
 * @param {number[][]} connections
 * @param {number[][]} queries
 * @return {number[]}
 */

题目给了一个数字 c 表示有 c 个电站，电站默认是上线状态

connections 表示两两电站之间的联通关系

queries 表示操作，有两种：

1. [1, x]：表示查找 x 电站，如果 x 电站在线上则返回 x，否则返回与其联通的 id 最小的电站，如果找不到则返回 -1
2. [2, x]：表示将 x 电站下线

解题思路

根据题目描述，我们自然而然的能够把一个个电站归类为一个个的集合，集合内的电站要么直接要么间接的有联通关系

当我们要查找某个电站的时候，我们要经过以下步骤：

1. 判断该电站是否是上线状态，如果是直接返回电站的 id
2. 如果不是我们需要找到该电站所属的集合，然后查找其中最小的上线电站 id 返回

我们可以用一个数组来保存 c 个电站的上线状态

找到所属集合以及查找最小的电站 id 我们有两种方法来做：小顶堆以及并查集

下面我们展示小顶堆的方法：

Javascript

/**
 * @param {number} c
 * @param {number[][]} connections
 * @param {number[][]} queries
 * @return {number[]}
 */
var processQueries = function (c, connections, queries) {
    const online = new Array(c + 1).fill(true)
    const belongs = new Array(c + 1).fill(-1)
    // use to keep wvery minHeap
    const heaps = []
    const connectionMap = new Map()

    // a dfs helper function to update belongs and heaps
    const helper = (station, heap) => {
        belongs[station] = heaps.length
        heap.enqueue(station)
        for (const s of (connectionMap.get(station) || [])) {
            if (belongs[s] < 0) {
                helper(s, heap)
            }
        }
    }

    // update connectionMap
    for (const [s1, s2] of connections) {
        if (connectionMap.has(s1)) {
            connectionMap.get(s1).push(s2)
        } else {
            connectionMap.set(s1, [s2])
        }
        if (connectionMap.has(s2)) {
            connectionMap.get(s2).push(s1)
        } else {
            connectionMap.set(s2, [s1])
        }
    }

    // build a minHeap for every power grid
    for (let i = 1; i <= c; i++) {
        if (belongs[i] >= 0) {
            continue
        }
        const minHeap = new PriorityQueue((a, b) => a - b)
        helper(i, minHeap)
        heaps.push(minHeap)
    }

    const res = []
    // handles the ops
    for (const [op, station] of queries) {
        if (op === 2) {
            online[station] = false
            continue
        }
        if (online[station]) {
            res.push(station)
        } else {
            // get the target heap
            const heap = heaps[belongs[station]]
            while (!heap.isEmpty() && !online[heap.front()]) {
                heap.dequeue()
            }
            res.push(heap.isEmpty() ? -1 : heap.front())
        }
    }

    return res
};