Power Grid Maintenance
Problem
c power stations (ids 1…c) are linked by bidirectional cables in connections; directly or indirectly connected stations form a power grid. All stations start online. Process queries: [1, x] is a maintenance check — if x is online it answers itself, otherwise the online station with the smallest id in x's grid answers, or -1 if its grid has none online. [2, x] takes station x offline. Return the answers to every [1, x] query in order.
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]import heapq
def processQueries(c, connections, queries):
parent = list(range(c + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
for u, v in connections: # union connected stations
parent[find(u)] = find(v)
heaps = {} # component root -> min-heap of ids
for s in range(1, c + 1):
heaps.setdefault(find(s), []).append(s)
for h in heaps.values():
heapq.heapify(h)
online = [True] * (c + 1)
res = []
for t, x in queries:
if t == 2:
online[x] = False # take station x offline
elif online[x]:
res.append(x) # x answers its own check
else:
h = heaps[find(x)]
while h and not online[h[0]]: # discard offline tops lazily
heapq.heappop(h)
res.append(h[0] if h else -1)
return resfunction processQueries(c, connections, queries) {
const parent = Array.from({ length: c + 1 }, (_, i) => i);
function find(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x; // root with path compression
}
for (const [u, v] of connections) parent[find(u)] = find(v);
const heaps = new Map(); // root -> min-heap of ids
for (let s = 1; s <= c; s++) {
const r = find(s);
if (!heaps.has(r)) heaps.set(r, new MinHeap());
heaps.get(r).push(s);
}
const online = new Array(c + 1).fill(true);
const res = [];
for (const [t, x] of queries) {
if (t === 2) { online[x] = false; } // take station x offline
else if (online[x]) { res.push(x); } // x answers its own check
else {
const h = heaps.get(find(x));
while (h.size() && !online[h.peek()]) h.pop(); // drop offline tops
res.push(h.size() ? h.peek() : -1);
}
}
return res;
}int[] processQueries(int c, int[][] connections, int[][] queries) {
int[] parent = new int[c + 1];
for (int i = 0; i <= c; i++) parent[i] = i;
for (int[] e : connections) parent[find(parent, e[0])] = find(parent, e[1]);
Map<Integer, PriorityQueue<Integer>> heaps = new HashMap<>();
for (int s = 1; s <= c; s++) // group ids by component root
heaps.computeIfAbsent(find(parent, s), k -> new PriorityQueue<>()).add(s);
boolean[] online = new boolean[c + 1];
Arrays.fill(online, true);
List<Integer> res = new ArrayList<>();
for (int[] q : queries) {
int x = q[1];
if (q[0] == 2) online[x] = false; // take station x offline
else if (online[x]) res.add(x); // x answers its own check
else {
PriorityQueue<Integer> h = heaps.get(find(parent, x));
while (!h.isEmpty() && !online[h.peek()]) h.poll(); // drop offline
res.add(h.isEmpty() ? -1 : h.peek());
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }vector<int> processQueries(int c, vector<vector<int>>& connections,
vector<vector<int>>& queries) {
vector<int> parent(c + 1);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x; // root with path compression
};
for (auto& e : connections) parent[find(e[0])] = find(e[1]);
unordered_map<int, priority_queue<int, vector<int>, greater<int>>> heaps;
for (int s = 1; s <= c; s++) heaps[find(s)].push(s); // min-heaps per grid
vector<bool> online(c + 1, true);
vector<int> res;
for (auto& q : queries) {
int x = q[1];
if (q[0] == 2) online[x] = false; // take station x offline
else if (online[x]) res.push_back(x);
else {
auto& h = heaps[find(x)];
while (!h.empty() && !online[h.top()]) h.pop(); // drop offline tops
res.push_back(h.empty() ? -1 : h.top());
}
}
return res;
}Explanation
The grid structure never changes, so we precompute it once. We use union-find (disjoint set union) to merge every pair of directly connected stations; afterwards two stations share a root exactly when they belong to the same power grid. Path compression keeps find near-constant time.
For each power grid we keep a min-heap of the station ids it contains, keyed by the grid's root. The smallest element of a heap is always the lowest id in that grid — precisely what a maintenance check wants, provided it is still online.
A type-2 query just flips online[x] to false. We do not remove x from any heap immediately, because heaps don't support cheap arbitrary removal. Instead we delete lazily.
A type-1 query for station x has three cases: if x itself is online it answers its own check; otherwise we look at its grid's heap and pop stale tops — any id at the top that is already offline gets discarded. The first online id left at the top is the answer; if the heap empties, the grid has no operational station and we return -1.
Each station is popped at most once across all queries, so the lazy cleanup is amortized: the whole run is O((c + q) log c).
Example: stations 1–5 form one grid with heap [1,2,3,4,5]. [1,3] → 3 online, answer 3. [2,1] marks 1 offline. [1,1] → 1 offline, pop stale 1, top is 2 → answer 2. [2,2] marks 2 offline. [1,2] → 2 offline, pop stale 2, top is 3 → answer 3. Result [3,2,3].