时间轴

2025-11-07

init

题目：

P3607 电网维护

https://leetcode.cn/problems/power-grid-maintenance/description/?envType=daily-question&envId=2025-11-07

DFS+最小堆+懒删除

下面这个代码会WA，原因是维护了每个结点能到达的所有结点为一个最小堆，如果使某个结点下线，只从所有能到达该结点的堆中懒删除了该结点，而没有考虑需要从该节点经过才能到达的结点，这类结点也不能可达。而且：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <vector>
#include <unordered_set>
#include <queue>
#include <unordered_map>
#include <stack>
#include <algorithm>

using std::vector;
using std::unordered_set;
using std::priority_queue;
using std::unordered_map;
using std::stack;

typedef priority_queue<int, vector<int>, std::greater<int> > MinHeap;
class Solution {
    public:
	vector<int> processQueries(int c, vector<vector<int> > &connections, vector<vector<int> > &queries)
	{
		vector<bool> work_states = vector<bool>(c, true);

		vector<MinHeap> neighbors_heap = vector<MinHeap>(c, MinHeap());
		vector<unordered_set<int> > to_be_deleted = vector<unordered_set<int> >(c);

		unordered_map<int, vector<int> > graph;
		vector<int> res;
		int i = 0, j = 0, n, connection_size = connections.size();
		int p_stat1, p_stat2;

		// 建图
		for (i = 0; i < c; i++) { // 编号从0到c-1
			graph[i] = vector<int>();
		}

		for (i = 0; i < connection_size; i++) {
			p_stat1 = connections[i][0] - 1; // 从0开始编号
			p_stat2 = connections[i][1] - 1;
			graph[p_stat1].push_back(p_stat2);
			graph[p_stat2].push_back(p_stat1);
		}

		// 填充neighbors_heap
		int top;
		vector<bool> visited = vector<bool>(c, false);
		vector<vector<int> > graph_components;
		for (i = 0; i < c; i++) { // 深度优先遍历
			if (visited[i]) {
				continue;
			}
			stack<int> st;
			st.push(i);
			vector<int> curr_graph;
			while (!st.empty()) {
				top = st.top();
				st.pop();
				if (!visited[top]) {
					visited[top] = true;
					curr_graph.push_back(top);
				}

				for (int node : graph[top]) {
					if (!visited[node]) {
						st.push(node);
					}
				}
			}
			graph_components.push_back(curr_graph);
		}

		for (vector<int> v : graph_components) { //图的每个连通分量
			n = v.size();
			for (i = 0; i < n; i++) {
				for (j = 0; j < n; j++) {
					if (j == i) {
						continue;
					}
					neighbors_heap[v[i]].push(v[j]);
				}
			}
		}

		int query_size = queries.size();
		int ops, p_stat;
		bool flag;
		for (i = 0; i < query_size; i++) {
			ops = queries[i][0];
			p_stat = queries[i][1] - 1;
			if (ops == 1) { // maintence
				if (work_states[p_stat]) { // p_stat在线，自行解决
					res.push_back(p_stat + 1);
				} else { //它的neighbor_heap中最小的
					flag = true;
					while (!neighbors_heap[p_stat].empty()) {
						top = neighbors_heap[p_stat].top();
						if (!to_be_deleted[p_stat].count(top)) { // 不需要删除
							res.push_back(top + 1);
							flag = false;
							break;
						} else {
							neighbors_heap[p_stat].pop();
							to_be_deleted[p_stat].erase(top);
						}
					}
					if (flag) {
						res.push_back(-1);
					}
				}

			} else if (ops == 2) { // goes offline
				work_states[p_stat] = false; // p_stat标记为offline
				for (int ps : graph[p_stat]) { // 所有指向p_stat标记为删除
					to_be_deleted[ps].insert(p_stat);
				}
			}
		}
		return res;
	}
};

官方正解：

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
class 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
80
class 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;
    }
};