Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Taking a station offline does not change which power grid it belongs to. Compute connected components once, then maintain the online members of each component and a way to find their smallest ID. Offline entries can be removed from a heap lazily when they reach its top.

Approach

Traverse the connection graph, assigning every station a component ID, including isolated stations. For each component, build an online-membership set and a min-heap of all its station IDs.

For an offline query, remove the station from its online set if present. For a maintenance query, return the requested station itself if it is online. Otherwise discard offline IDs from its component's heap top until the top is online or the heap is empty. Return that top ID, or -1 if no online station remains.

An offline station never becomes online again, so a discarded heap entry is never needed later. Each entry is popped at most once across all queries, and component membership remains valid throughout.

class Solution:
    def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        #  preprocess power grids
        adj = defaultdict(list)

        for a, b in connections:
            adj[a].append(b)
            adj[b].append(a)
        
        def dfs(id, pg_id):
            seen.add(id)
            pg.append(id) # add node to pg
            id_pg[id] = pg_id # associate pg number with node

            for nei in adj[id]:
                if nei not in seen:
                    dfs(nei, pg_id)
        
        seen = set()
        id_pg = {}
        pgs = {}
        pgs_s = {}
        pg_id = 1

        for id in range(1, c + 1):
            if id in seen: continue
            pg = []
            dfs(id, pg_id)
            pgs_s[pg_id] = set(pg)
            heapq.heapify(pg)
            pgs[pg_id] = pg
            pg_id += 1

        # build result
        res = []
        for t, id in queries:
            pgi = id_pg[id]
            pg_set = pgs_s[pgi]
            pg_heap = pgs[pgi]

            if t == 1:
                if id in pg_set:
                    res.append(id)
                else:
                    while pg_heap and not pg_heap[0] in pg_set: heapq.heappop(pg_heap)
                    if pg_heap: res.append(pg_heap[0])
                    else: res.append(-1)
            else:
                if id in pg_set: pg_set.remove(id)
        
        return res

Complexity analysis

Let C be station count, E connection count, and Q query count. Total time: O(C + E + Q + C log C) because each component is heapified and each offline heap entry is lazily popped at most once. Auxiliary space: O(C + E), excluding the returned result. Implementation caveat: Python's recursive component DFS can reach depth C and may exceed the recursion limit at the allowed C = 100,000; JavaScript uses an explicit stack.