What pattern does Power Grid Maintenance follow?

It uses array scanning plus hash lookup to track connected components and efficiently process online/offline queries.

How do I handle a query for a station that is offline?

Check the offline hash set first; if the station is offline, return -1 immediately.

Can this problem be solved without DFS or BFS?

Direct DFS/BFS assignment is optimal for component IDs, but Union-Find can also be used to maintain connectivity dynamically.

What happens when multiple stations go offline consecutively?

Update the offline hash for each station and adjust component sizes accordingly; connectivity queries then reflect the current state.

How does GhostInterview optimize processing for Power Grid Maintenance?

It precomputes component IDs and uses hash lookups to answer connectivity queries instantly while handling offline updates efficiently.

#3607

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

电网维护

给你一个整数 c ，表示 c 个电站，每个电站有一个唯一标识符 id ，从 1 到 c 编号。这些电站通过 n 条双向电缆互相连接，表示为一个二维数组 connections ，其中每个元素 connections[i] = [u i , v i ] 表示电站 u i 和电站 v i 之间的连…

数组哈希表深度优先搜索广度优先搜索并查集

题目描述

给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。

这些电站通过 n 条双向电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [u_i, v_i] 表示电站 u_i 和电站 v_i 之间的连接。直接或间接连接的电站组成了一个电网。

最初，所有电站均处于在线（正常运行）状态。

另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ：

[1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一电网中 编号最小 的在线电站解决。如果该电网中 不存在 任何在线电站，则返回 -1。
[2, x]：电站 x 离线（即变为非运行状态）。

返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。

注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

示例 1：

输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

输出： [3,2,3]

解释：

最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。
查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。
查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。
查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。
查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。
查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。

示例 2：

输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

输出： [1,-1]

解释：

没有连接，因此每个电站是一个独立的电网。
查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。
查询 [2,1]：电站 1 离线。
查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。

提示：

1 <= c <= 10⁵
0 <= n == connections.length <= min(10⁵, c * (c - 1) / 2)
connections[i].length == 2
1 <= u_i, v_i <= c
u_i != v_i
1 <= queries.length <= 2 * 10⁵
queries[i].length == 2
queries[i][0] 为 1 或 2。
1 <= queries[i][1] <= c

lightbulb

解题思路

方法一：并查集 + 有序集合

我们可以使用并查集（Union-Find）来维护电站之间的连接关系，从而确定每个电站所属的电网。对于每个电网，我们使用有序集合（如 Python 中的 SortedList、Java 中的 TreeSet 或 C++ 中的 std::set）来存储该电网中所有在线的电站编号，以便能够高效地查询和删除电站。

具体步骤如下：

初始化并查集，处理所有连接关系，将连接的电站合并到同一个集合中。
为每个电网创建一个有序集合，初始时将所有电站编号加入对应电网的集合中。
遍历查询列表：
- 对于查询 $[1, x]$ $[1, x]$ ，首先找到电站 $x$ $x$ 所属的电网根节点，然后检查该电网的有序集合：
  - 如果电站 $x$ 在线（存在于集合中），则返回 $x$ 。
  - 否则，返回集合中的最小编号电站（如果集合非空），否则返回 -1。
- 对于查询 $[2, x]$ ，找到电站 $x$ 所属的电网根节点，并将电站 $x$ 从该电网的有序集合中删除，表示该电站离线。
最后，返回所有类型为 $[1, x]$ 的查询结果。

时间复杂度 $O((c + n + q) \log c)$ ，空间复杂度 $O(c)$ 。其中 $c$ 是电站数量，而 $n$ 和 $q$ 分别是连接数量和查询数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def processQueries(
        self, c: int, connections: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        uf = UnionFind(c + 1)
        for u, v in connections:
            uf.union(u, v)
        st = [SortedList() for _ in range(c + 1)]
        for i in range(1, c + 1):
            st[uf.find(i)].add(i)
        ans = []
        for a, x in queries:
            root = uf.find(x)
            if a == 1:
                if x in st[root]:
                    ans.append(x)
                elif len(st[root]):
                    ans.append(st[root][0])
                else:
                    ans.append(-1)
            else:
                st[root].discard(x)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the initial component assignment via DFS/BFS, O(c + n), plus O(1) per query using hash lookups. Space complexity includes storing component IDs, offline hash set, and component sizes, O(c + n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate efficiently maps stations to connected components using DFS/BFS.
question_mark
Uses a hash set or array for quick online/offline checks.
question_mark
Processes queries without recomputing entire connectivity each time.

warning

常见陷阱

外企场景

error
Forgetting to check if a station is offline before reporting size.
error
Recomputing connectivity naively on each query leading to TLE.
error
Incorrectly updating component sizes after a station goes offline.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Queries may include reconnect operations instead of only offline.
arrow_right_alt
Connections might form multiple disconnected grids initially.
arrow_right_alt
Use weighted connections or additional station attributes affecting connectivity.

help

常见问题

外企场景

继续练习

#3493 属性图 #2368 受限条件下可到达节点的数目 #928 尽量减少恶意软件的传播 II