LeetCode Daily Problem P3607 Power Grid Maintenance

---

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 is taken offline, it only lazily deletes that node from the heaps of all nodes 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.

#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 the graph
		for (i = 0; i < c; i++) { // Numbered from 0 to c-1
			graph[i] = vector<int>();
		}

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

		// Populate neighbors_heap
		int top;
		vector<bool> visited = vector<bool>(c, false);
		vector<vector<int> > graph_components;
		for (i = 0; i < c; i++) { // Depth-first traversal
			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 is online, handle it directly
					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; // Mark p_stat as offline
				for (int ps : graph[p_stat]) { // All references to p_stat are marked for deletion
					to_be_deleted[ps].insert(p_stat);
				}
			}
		}
		return res;
	}
};

Official solution:

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 says the grid structure is fixed, i.e., going offline does not change connectivity. Therefore, we can think in reverse: if we view 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 a Disjoint Set Union (DSU) to maintain the minimum online number in each power grid.
  Official solution:

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