Cover image for LeetCode Daily Problem P3607 Power Grid Maintenance

LeetCode Daily Problem P3607 Power Grid Maintenance

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-11-07

init

Problem:

P3607 Power Grid Maintenance

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

DFS + Min-Heap + Lazy Deletion

The following code will get WA because it maintains a min-heap of all nodes reachable from each node. If a node goes offline, it only lazily deletes that node from all heaps that can reach it, without considering nodes that can only be reached through that node; such nodes also become unreachable. Moreover: the structure of the power grid is fixed; offline (non-operational) nodes still belong to their power grid, and offline operations do not change the connectivity of the grid.

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;

		// Build Graph
		for (i = 0; i < c; i++) { // Numbering from 0 to c-1
			graph[i] = vector<int>();
		}

		for (i = 0; i < connection_size; i++) {
			p_stat1 = connections[i][0] - 1; // Number starting from 0
			p_stat2 = connections[i][1] - 1;
			graph[p_stat1].push_back(p_stat2);
			graph[p_stat2].push_back(p_stat1);
		}

		// Fill neighbors_heap
		int top;
		vector<bool> visited = vector<bool>(c, false);
		vector<vector<int> > graph_components;
		for (i = 0; i < c; i++) { // Depth-First Search
			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) { //Each connected component of the graph
			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 online, solve it yourself
					res.push_back(p_stat + 1);
				} else { //the smallest in its neighbor_heap
					flag = true;
					while (!neighbors_heap[p_stat].empty()) {
						top = neighbors_heap[p_stat].top();
						if (!to_be_deleted[p_stat].count(top)) { // no need to delete
							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 marked as offline
				for (int ps : graph[p_stat]) { // all pointers to p_stat marked for deletion
					to_be_deleted[ps].insert(p_stat);
				}
			}
		}
		return res;
	}
};

Official solution:

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

Disjoint Set Union (DSU)

This method is a bit hard to think of:

Difficulty: operations are performed online, and offline operations affect subsequent queries.
But the problem states that the power grid structure is fixed, meaning offline does not change connectivity. Therefore, we can think in reverse: if we look at the operations from back to front, ‘offline’ becomes ‘back online’!
So the algorithm uses a reverse process:

  • First preprocess the final state of all nodes (which ones are offline at the end).
  • Then process from the last operation backwards.
  • Treat ‘offline’ as ‘back online’.
  • Use Disjoint Set Union (DSU) to maintain the smallest online number in each power grid.
    Official solution:
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;
    }
};