commit 6728b04ba3c11d4af85d03bc242a3e4451cd4bab
parent bbedc001ddf63b8c4db75767daa3fca558f46261
Author: Jack Sangdahl <jack@pngu.org>
Date: Wed, 5 Nov 2025 22:39:12 -0700
3607. power grid maintenance
Diffstat:
2 files changed, 161 insertions(+), 0 deletions(-)
diff --git a/power_grid_maintenance.c b/power_grid_maintenance.c
@@ -0,0 +1,95 @@
+// 3607. Power Grid Maintenance
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'c' representing power stations, each with a unique
+ * identifier 'id' from 1 to 'c'. these stations are interconnected via 'n'
+ * bidirectional cables, represented by a 2 array 'connections' where each
+ * element 'connections[i] = [u_i, v_i]' indicates a connection between station
+ * 'u_i' and 'v_i'. stations that are directly or indirectly connected form a
+ * power grid. initially, all stations are online (operational). you are also
+ * given a 2d integer array 'quries' where each query is one of the following
+ * types: '[1, x]': a maintenance check is requested for station 'x'. if station
+ * 'x' is online, it resolves the check by itself. if station 'x' is offline,
+ * the check is resolved by the operational station with the smallest 'id' in
+ * the same power grid as 'x'. if no operational station exists in that grid,
+ * return -1. '[2, x]': station 'x' goes offline. return an array of integers
+ * representing the results of each query of type '[1, x]' in the order they
+ * appear.
+ */
+
+int find(int *parent, int x) {
+ if (parent[x] != x)
+ parent[x] = find(parent, parent[x]);
+ return parent[x];
+}
+
+int *processQueries(int c, int **connections, int connectionsSize,
+ int *connectionsColSize, int **queries, int queriesSize,
+ int *queriesColSize, int *returnSize) {
+ int *parent = (int *)malloc((c + 1) * sizeof(int));
+ for (int i = 0; i <= c; i++)
+ parent[i] = i;
+ for (int i = 0; i < connectionsSize; i++) {
+ int a = connections[i][0], b = connections[i][1];
+ int aa = find(parent, a), bb = find(parent, b);
+ if (aa != bb)
+ parent[bb] = aa;
+ }
+ int *next_node = (int *)calloc(c + 1, sizeof(int));
+ int *cmp_min = (int *)calloc(c + 1, sizeof(int));
+ int *prev = (int *)calloc(c + 1, sizeof(int));
+ for (int i = 1; i <= c; i++) {
+ int r = find(parent, i);
+ if (!cmp_min[r])
+ cmp_min[r] = i;
+ else
+ next_node[prev[r]] = i;
+ prev[r] = i;
+ }
+ int *offline = (int *)calloc(c + 1, sizeof(int)), ri = 0;
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ for (int i = 0; i < queriesSize; i++) {
+ int t = queries[i][0], x = queries[i][1], r = find(parent, x);
+ if (t == 1) {
+ if (!offline[x])
+ ans[ri++] = x;
+ else
+ ans[ri++] = cmp_min[r] ? cmp_min[r] : -1;
+ } else {
+ if (offline[x])
+ continue;
+ offline[x] = 1;
+ if (cmp_min[r] == x) {
+ int y = next_node[x];
+ while (y && offline[y])
+ y = next_node[y];
+ cmp_min[r] = y;
+ }
+ }
+ }
+ free(parent);
+ free(next_node);
+ free(cmp_min);
+ free(prev);
+ free(offline);
+ *returnSize = ri;
+ return ans;
+}
+
+int main() {
+ int c1i[4][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}},
+ q1i[5][2] = {{1, 3}, {2, 1}, {1, 1}, {2, 2}, {1, 2}};
+ struct two_d_arr *c1 =
+ two_d_arr_init(ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i);
+ struct two_d_arr *q1 =
+ two_d_arr_init(ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ int rs1, *pq1 = processQueries(5, c1->arr, c1->row_size, c1->col_size,
+ q1->arr, q1->row_size, q1->col_size, &rs1);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pq1[i]); // expect: 3 2 3
+ printf("\n");
+ free(pq1);
+ two_d_arr_free(c1);
+ two_d_arr_free(q1);
+}
diff --git a/power_grid_maintenance.py b/power_grid_maintenance.py
@@ -0,0 +1,66 @@
+# 3607. Power Grid Maintenance
+from collections import defaultdict
+
+"""
+you are given an integer 'c' representing power stations, each with a unique
+identifier 'id' from 1 to 'c'. these stations are interconnected via 'n'
+bidirectional cables, represented by a 2 array 'connections' where each
+element 'connections[i] = [u_i, v_i]' indicates a connection between station
+'u_i' and 'v_i'. stations that are directly or indirectly connected form a
+power grid. initially, all stations are online (operational). you are also
+given a 2d integer array 'quries' where each query is one of the following
+types: '[1, x]': a maintenance check is requested for station 'x'. if station
+'x' is online, it resolves the check by itself. if station 'x' is offline,
+the check is resolved by the operational station with the smallest 'id' in
+the same power grid as 'x'. if no operational station exists in that grid,
+return -1. '[2, x]': station 'x' goes offline. return an array of integers
+representing the results of each query of type '[1, x]' in the order they
+appear.
+"""
+
+
+class Solution(object):
+ def processQueries(self, c, connections, queries):
+ """
+ :type c: int
+ :type connections: List[List[int]]
+ :type queries: List[List[int]]
+ :rtype: List[int]
+ """
+ graph = defaultdict(list)
+ for u, v in connections:
+ graph[u].append(v)
+ graph[v].append(u)
+ online = [True] * (c + 1)
+ ans = []
+
+ def dfs(x, vis):
+ vis.add(x)
+ for i in graph[x]:
+ if i not in vis:
+ dfs(i, vis)
+
+ for t, x in queries:
+ if t == 1:
+ if online[x]:
+ ans.append(x)
+ else:
+ vis = set()
+ dfs(x, vis)
+ online_nodes = [i for i in vis if online[i]]
+ ans.append(min(online_nodes) if online_nodes else -1)
+ else:
+ online[x] = False
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.processQueries(
+ c=5,
+ connections=[[1, 2], [2, 3], [3, 4], [4, 5]],
+ queries=[[1, 3], [2, 1], [1, 1], [2, 2], [1, 2]],
+ )
+ )
+ print(obj.processQueries(c=3, connections=[], queries=[[1, 1], [2, 1], [1, 1]]))
