• Leetcode 3607. Power Grid Maintenance
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3607. Power Grid Maintenance

1. 解题思路

这一题思路上首先是一个DSU的思路，将所有的连通网络计算出来，并对每一个网络的节点进行归类。然后我们需要对每一个网络当中的节点的状态进行一下维护，这里我们采用的是有序数组的方式，通过二分查找进行增删操作，然后每次query就是找出其中点的状态并进行更新。

当query操作为1时，我们就是要判断一下目标点的状态，如果当前其状态为在线，就直接返回其结果，反之在对应的簇当中返回最小节点或者-1；如果query操作为2时，我们将目标点下线并更新对应的簇当中的有效节点即可。

而关于DSU的相关内容，这里就不具体展开了，网上资料很多，我自己也有一篇水文《经典算法：并查集（DSU）结构简介》作为备忘，有兴趣的读者自己查查了解一下好了。

2. 代码实现

给出python代码实现如下：

class DSU:def __init__(self, N):self.root = [i for i in range(N)]def find(self, k):if self.root[k] != k:self.root[k] = self.find(self.root[k])return self.root[k]def union(self, a, b):x = self.find(a)y = self.find(b)if x != y:self.root[y] = xreturnclass Solution:def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:dsu = DSU(c+1)for u, v in connections:dsu.union(u, v)clusters = defaultdict(list)for i in range(1, c+1):u = dsu.find(i)clusters[u].append(i)ans = []for op, idx in queries:u = dsu.find(idx)i = bisect.bisect_left(clusters[u], idx)if op == 1:if i < len(clusters[u]) and clusters[u][i] == idx:ans.append(idx)elif len(clusters[u]) > 0:ans.append(clusters[u][0])else:ans.append(-1)else:if i < len(clusters[u]) and clusters[u][i] == idx:clusters[u].pop(i)return ans

提交代码评测得到：耗时1388ms，占用内存101.67MB。