Problem Statement in English

You’re given a power grid with c cities (numbered from 1 to c) and a list of connections, where each connection connects two cities. The power grid is represented as an undirected graph. Each city can be connected to multiple other cities through these connections. Each city belongs to a connected component in the graph. The component may consist of one or more cities.

You need to process a series of queries. Each query can be of two types:

  1. Type 1 Query: Given a city v, find the city with the smallest city number that is in the same connected component as city v. If no such city exists, return -1.
  2. Type 2 Query: Given a city v, city v is taken down for maintenance, but is still part of its component, meaning it can still be reached from other cities in the same component.

Approach

The problem can be solved using Depth-First Search (DFS) to identify connected components in the graph.

We will maintain a mapping of each city to its connected component and use a sorted data structure to efficiently retrieve and remove cities in each component.

Solution in Python


class Solution:
    def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
        adjList = defaultdict(list)
        gridHm = {}
        sgl = defaultdict(SortedList)
        seen = set()
        res = []

        for a, b in connections:
            adjList[a].append(b)
            adjList[b].append(a)

        def dfs(n, grid):
            gridHm[n] = grid
            sgl[grid].add(n)
            seen.add(n)

            for nei in adjList[n]:
                if nei not in seen:
                    dfs(nei, grid)

        uid = 0
        for i in range(1, c + 1):
            if i not in seen:
                dfs(i, uid)
                uid += 1

        for m, v in queries:
            if m == 1:
                if v in sgl[gridHm[v]]:
                    res.append(v)
                elif sgl[gridHm[v]]:
                    res.append(sgl[gridHm[v]][0])
                else:
                    res.append(-1)
            else:
                sgl[gridHm[v]].discard(v)

        return res

Complexity

  • Time:

  • The data structure build takes logarithmic time for each insertion into the sorted list, leading to a total time complexity of $O((C + Q) \log C)$, where $C$ is the number of connections and $Q$ is the number of queries.

  • Each query operation (both type 1 and type 2) involves logarithmic time complexity for deletion and constant time for the rest.

  • Space: $O(C)$, where $C$ is the number of connections, for storing the adjacency list and other data structures.

And we are done.