题目
给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。
这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。
最初，所有 电站均处于在线（正常运行）状态。
另给你一个二维数组 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^50 <= n == connections.length <= min(105, c * (c - 1) / 2)connections[i].length == 21 <= ui, vi <= cui != vi1 <= queries.length <= 2 * 10%5queries[i].length == 2queries[i][0]为 1 或 2。1 <= queries[i][1] <= c
解题思路
最朴素的想法是：对每个查询 [1, x]，在整张图里做一次 BFS/DFS 找到和 x 处于同一电网（连通分量）的所有节点，然后在这些节点里找 最小编号的在线电站；对 [2, x] 就把 x 标为离线即可。
- 性能分析： 设电站数为 (C)、电缆数为 (N)、查询数为 (Q)。一次 BFS/DFS 的时间是 (O(C+N))。如果很多查询都是
[1, x]，最坏会到 (O(Q\cdot (C+N)))。当三者都可达 (10^5) 量级时，这是不可接受的（必超时）。 - 关键观察： 题目已经强调 “离线不会改变连接性”，也就是说图的连通分量是静态的。 👉 因此，只需要在开头 一次性 把所有连通分量（电网）分出来，之后就绝不再做整图搜索。
- 对策：空间换时间（预处理 + 快速查询）
- 连通分量预处理：用 并查集（Union-Find/DSU） 或一次性 BFS/DFS，把每个电站映射到一个电网 ID（根）。这步只做一遍，复杂度 (O(C+N))。
- 电网内“最小在线编号”的快速获取：为每个电网维护一个 最小堆（min-heap），把该电网内的所有节点编号都放进去。堆顶就是“最小编号”。
- 在线状态：用一个布尔数组
online[1..C]标记在线/离线。下线时只改布尔值，不立刻改堆。 - 查询
[1, x]：- 若
x在线，直接返回x； - 若
x离线，则到x的电网堆中“懒惰删除”离线堆顶，直到堆顶为在线节点或堆空：- 堆空 → 返回
-1； - 否则 → 返回堆顶。
- 堆空 → 返回
- 若
- 查询
[2, x]：把online[x] = False（不从堆里删除x，等下次需要取堆顶再顺便清理——懒删除）。
- 为什么用堆？ 我们需要“电网内最小在线编号”的即时查询。维护有序集合的方式很多（如
TreeSet/set），但用最小堆配合懒删除足够简单高效：- 取最小：摊还 (O(\log C))；
- 离线后不做删除：把成本推迟到真正需要时；每个节点最多被弹出一次，全程总开销 (O(C \log C))。
总时间复杂度：
- 预处理连通分量：(O(C+N))；
- 建堆：把每个电网的节点各入堆一次，总计 (O(C)) 建堆（摊还）或 (O(C \log C))（逐个 push）；
- 处理 (Q) 次查询：
[2, x]：(O(1))；[1, x]：均摊至 (O(\log C))（堆顶清理 + 取顶）；
- 综合：(O(C+N) + O(C) + O(Q\log C))（或写成 (O((C+N+Q)\log C)) 也常见）。对 (10^5) 量级可轻松通过。
懒删除的堆技巧
链表题里删除需要“前驱指针”与“哨兵节点”； 在本题里，删除（下线）对应的是“把节点从候选集合里移除”。如果我们真的在堆里做“任意位置删除”，实现会复杂、常数也大。更优雅的办法**是：
- 懒惰删除（Lazy Removal）：
- 下线时：只做
online[x] = False，不动堆。 - 需要取“最小在线编号”时：
- 看看堆顶 (h[0]) 是否在线；
- 若离线，就
heappop(h)弹掉，继续看新的堆顶； - 重复直到堆顶在线或堆空。
- 这样每个节点最多被弹出一次，总弹出次数 ≤ C，均摊下来非常高效。
- 下线时：只做
- 并查集的作用（对标链表里“指针指向关系”）： 链表里“是否相连”由
next指针决定；本题里“是否在同一电网”由连通性决定。 我们用 DSU 一次性 固定每个节点的“代表根”，就像给每个节点打上了“电网标签”。 后续任何查询[1, x]、[2, x]都可以 O(1) 地定位到“电网 ID = find(x)”，从而直达对应的最小堆做操作。
实现要点小结：
- DSU 预处理：
find(x)返回电网 ID（根）。 - 为每个电网建一个最小堆：初始把该电网的所有节点都放入；
- 在线数组：
online[x] = True/False； - 查询：
[1, x]：- 若
online[x]：返回x； - 否则：到
comp_heap[find(x)]里懒删离线堆顶，取当前堆顶或-1；
- 若
[2, x]：online[x] = False（不操作堆）。
具体代码
CPP
class Solution {
public:
vector<int> processQueries(int c, vector<vector<int>>& connections, vector<vector<int>>& queries) {
// --- 并查集（Union-Find） ---
vector<int> parent(c + 1), rnk(c + 1, 0);
iota(parent.begin(), parent.end(), 0);
auto find = [&](int x) {
// 路径压缩
int y = x;
while (parent[y] != y) y = parent[y];
while (parent[x] != x) {
int p = parent[x];
parent[x] = y;
x = p;
}
return y;
};
auto uni = [&](int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
// 按秩合并
if (rnk[ra] < rnk[rb]) {
parent[ra] = rb;
} else if (rnk[ra] > rnk[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rnk[ra]++;
}
};
// 1) 用并查集合并所有连接（电网结构固定）
for (auto &e : connections) uni(e[0], e[1]);
// 2) 为每个电网维护一个最小堆（节点编号最小优先）
using MinHeap = priority_queue<int, vector<int>, greater<int>>;
vector<MinHeap> compHeap(c + 1);
for (int i = 1; i <= c; ++i) {
int r = find(i);
compHeap[r].push(i);
}
// 3) 记录在线状态，初始全部在线
vector<char> online(c + 1, 1);
// 4) 处理查询；对类型为 [1, x] 的查询输出结果
vector<int> ans;
ans.reserve(queries.size());
for (auto &q : queries) {
int t = q[0], x = q[1];
int r = find(x);
if (t == 1) {
// 维护检查：
if (online[x]) {
// 如果 x 在线，由自己处理
ans.push_back(x);
} else {
// 否则找该电网中编号最小的在线节点（懒惰删除离线节点）
auto &h = compHeap[r];
while (!h.empty() && !online[h.top()]) h.pop();
if (h.empty()) ans.push_back(-1);
else ans.push_back(h.top());
}
} else {
// 下线操作：
if (online[x]) {
online[x] = 0;
// 不必从堆中立即移除，查询时懒惰删除
}
}
}
return ans;
}
};
Python
from typing import List
import heapq
class Solution:
def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
# --- 并查集（Union-Find） ---
parent = list(range(c + 1))
rank = [0] * (c + 1)
def find(x: int) -> int:
# 路径压缩（加速查找根节点）
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> None:
# 按秩合并（rank小的挂到rank大的下面）
ra, rb = find(a), find(b)
if ra == rb:
return
if rank[ra] < rank[rb]:
parent[ra] = rb
elif rank[ra] > rank[rb]:
parent[rb] = ra
else:
parent[rb] = ra
rank[ra] += 1
# 第一步：通过并查集找到每个电站所在的连通分量（电网）
for u, v in connections:
union(u, v)
# 第二步：为每个连通分量维护一个最小堆（存储该电网中的所有节点）
comp_heap = {} # root -> 节点最小堆
for node in range(1, c + 1):
r = find(node)
if r not in comp_heap:
comp_heap[r] = []
comp_heap[r].append(node)
# 将每个电网内的节点建堆
for r in comp_heap:
heapq.heapify(comp_heap[r])
# 第三步：记录每个电站是否在线
online = [True] * (c + 1) # 下标从1开始
# 第四步：处理查询
res = []
for t, x in queries:
r = find(x)
if t == 1:
# 查询类型1：维护检查
if online[x]:
# 如果电站x在线，由自己处理
res.append(x)
else:
# 如果离线，查找同电网中编号最小的在线电站
h = comp_heap.get(r, [])
# 懒惰删除（lazy removal）：移除堆顶离线节点
while h and not online[h[0]]:
heapq.heappop(h)
res.append(h[0] if h else -1)
else:
# 查询类型2：将电站x设为离线
if online[x]:
online[x] = False
# 不需要立即从堆中删除，下一次查询时懒惰删除即可
return res