- 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。
