leetcode每日一题 P3607 电网维护
时间轴
2025-11-07
init
题目：
DFS+最小堆+懒删除
下面这个代码会WA，原因是维护了每个结点能到达的所有结点为一个最小堆，如果使某个结点下线，只从所有能到达该结点的堆中懒删除了该结点，而没有考虑需要从该节点经过才能到达的结点，这类结点也不能可达。而且：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。
1 |
|
官方正解：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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76class Vertex {
public:
int vertexId;
bool offline = false;
int powerGridId = -1;
Vertex() {}
Vertex(int id) : vertexId(id) {}
};
using PowerGrid = priority_queue<int, vector<int>, greater<int>>;
using Graph = vector<vector<int>>;
class Solution {
private:
vector<Vertex> vertices = vector<Vertex>();
void traverse(Vertex& u, int powerGridId, PowerGrid& powerGrid,
Graph& graph) {
u.powerGridId = powerGridId;
powerGrid.push(u.vertexId);
for (int vid : graph[u.vertexId]) {
Vertex& v = vertices[vid];
if (v.powerGridId == -1)
traverse(v, powerGridId, powerGrid, graph);
}
}
public:
vector<int> processQueries(int c, vector<vector<int>>& connections,
vector<vector<int>>& queries) {
Graph graph(c + 1);
vertices.resize(c + 1);
for (int i = 1; i <= c; i++) {
vertices[i] = Vertex(i);
}
for (auto& conn : connections) {
graph[conn.at(0)].push_back(conn.at(1));
graph[conn.at(1)].push_back(conn.at(0));
}
vector<PowerGrid> powerGrids;
for (int i = 1, powerGridId = 0; i <= c; i++) {
auto& v = vertices[i];
if (v.powerGridId == -1) {
PowerGrid powerGrid;
traverse(v, powerGridId, powerGrid, graph);
powerGrids.push_back(powerGrid);
powerGridId++;
}
}
vector<int> ans;
for (auto& q : queries) {
int op = q.at(0), x = q.at(1);
if (op == 1) {
if (!vertices[x].offline) {
ans.push_back(x);
} else {
auto& powerGrid = powerGrids[vertices[x].powerGridId];
while (!powerGrid.empty() &&
vertices[powerGrid.top()].offline) {
powerGrid.pop();
}
ans.push_back(!powerGrid.empty() ? powerGrid.top() : -1);
}
} else if (op == 2) {
vertices[x].offline = true;
}
}
return ans;
}
};
并查集
这个方法有点难想到：
困难点：操作是在线进行的，下线操作会影响后续查询。
但题目说电网结构固定，即下线不会改变连接性。于是，可以反向思考：如果我们把操作从后往前看，“下线”就会变成“重新上线”！
所以算法采用了一个反向过程：
- 先预处理所有节点的最终状态（哪些在最后是下线的）。
- 然后从最后一个操作往前处理。
- 把“下线”视作“重新上线”。
- 用并查集（DSU）维护每个电网中的最小在线编号。
官方解法：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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80class DSU {
public:
vector<int> parent;
DSU(int size) {
parent.resize(size);
iota(parent.begin(), parent.end(), 0);
}
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void join(int u, int v) { parent[find(v)] = find(u); }
};
class Solution {
public:
vector<int> processQueries(int c, vector<vector<int>>& connections,
vector<vector<int>>& queries) {
DSU dsu(c + 1);
for (auto& p : connections) {
dsu.join(p[0], p[1]);
}
vector<bool> online(c + 1, true);
vector<int> offlineCounts(c + 1, 0);
unordered_map<int, int> minimumOnlineStations;
for (auto& q : queries) {
int op = q[0], x = q[1];
if (op == 2) {
online[x] = false;
offlineCounts[x]++;
}
}
for (int i = 1; i <= c; i++) {
int root = dsu.find(i);
if (!minimumOnlineStations.count(root)) {
minimumOnlineStations[root] = -1;
}
int station = minimumOnlineStations[root];
if (online[i]) {
if (station == -1 || station > i) {
minimumOnlineStations[root] = i;
}
}
}
vector<int> ans;
for (int i = (int)queries.size() - 1; i >= 0; i--) {
int op = queries[i][0], x = queries[i][1];
int root = dsu.find(x);
int station = minimumOnlineStations[root];
if (op == 1) {
if (online[x]) {
ans.push_back(x);
} else {
ans.push_back(station);
}
}
if (op == 2) {
if (offlineCounts[x] > 1) {
offlineCounts[x]--;
} else {
online[x] = true;
if (station == -1 || station > x) {
minimumOnlineStations[root] = x;
}
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
wechat
alipay
