3607. Power Grid Maintenance

Description

You are given an integer c representing c power stations, each with a unique identifier id from 1 to c (1‑based indexing).

These stations are interconnected via n bidirectional cables, represented by a 2D array connections, where each element connections[i] = [ui, vi] indicates a connection between station ui and station vi. Stations that are directly or indirectly connected form a power grid.

Initially, all stations are online (operational).

You are also given a 2D array queries, where each query is one of the following two 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 (i.e., it becomes non-operational).

Return an array of integers representing the results of each query of type [1, x] in the order they appear.

Note: The power grid preserves its structure; an offline (non‑operational) node remains part of its grid and taking it offline does not alter connectivity.

 

Example 1:

Input: c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1,1],[2,2],[1,2]]

Output: [3,2,3]

Explanation:

• Initially, all stations {1, 2, 3, 4, 5} are online and form a single power grid.
• Query [1,3]: Station 3 is online, so the maintenance check is resolved by station 3.
• Query [2,1]: Station 1 goes offline. The remaining online stations are {2, 3, 4, 5}.
• Query [1,1]: Station 1 is offline, so the check is resolved by the operational station with the smallest id among {2, 3, 4, 5}, which is station 2.
• Query [2,2]: Station 2 goes offline. The remaining online stations are {3, 4, 5}.
• Query [1,2]: Station 2 is offline, so the check is resolved by the operational station with the smallest id among {3, 4, 5}, which is station 3.

Example 2:

Input: c = 3, connections = [], queries = [[1,1],[2,1],[1,1]]

Output: [1,-1]

Explanation:

• There are no connections, so each station is its own isolated grid.
• Query [1,1]: Station 1 is online in its isolated grid, so the maintenance check is resolved by station 1.
• Query [2,1]: Station 1 goes offline.
• Query [1,1]: Station 1 is offline and there are no other stations in its grid, so the result is -1.

 

Constraints:

• 1 <= c <= 105
• 0 <= n == connections.length <= min(105, c * (c - 1) / 2)
• connections[i].length == 2
• 1 <= ui, vi <= c
• ui != vi
• 1 <= queries.length <= 2 * 105
• queries[i].length == 2
• queries[i][0] is either 1 or 2.
• 1 <= queries[i][1] <= c

 

Solutions

Solution: Union Find

• Time complexity: O(c+n+q)
• Space complexity: O(c+q)

 

JavaScript

/**
 * @param {number} c
 * @param {number[][]} connections
 * @param {number[][]} queries
 * @return {number[]}
 */
const processQueries = function (c, connections, queries) {
  const OFFLINE = 2;
  const uf = new UnionFind(c + 1);
  const connected = Array.from({ length: c + 1 }, () => true);
  const powerGrids = Array.from({ length: c + 1 }, () => []);
  const girdPointer = Array.from({ length: c + 1 }, () => 0);
  const result = [];

  for (const [u, v] of connections) {
    uf.union(u, v);
  }

  for (let station = 1; station <= c; station++) {
    const group = uf.find(station);

    powerGrids[group].push(station);
  }

  for (const [type, station] of queries) {
    if (type === OFFLINE) {
      connected[station] = false;
      continue;
    }

    if (connected[station]) {
      result.push(station);
    } else {
      const group = uf.find(station);
      const powerGrid = powerGrids[group];
      let index = girdPointer[group];

      while (index < powerGrid.length && !connected[powerGrid[index]]) {
        index += 1;
      }

      girdPointer[group] = index;
      result.push(powerGrid[index] ?? -1);
    }
  }

  return result;
};

class UnionFind {
  constructor(n) {
    this.groups = Array.from({ length: n }, (_, index) => index);
    this.ranks = Array.from({ length: n }, () => 0);
  }

  find(x) {
    if (this.groups[x] === x) return x;

    this.groups[x] = this.find(this.groups[x]);

    return this.groups[x];
  }

  union(x, y) {
    const groupsX = this.find(x);
    const groupsY = this.find(y);

    if (groupsX === groupsY) return false;
    if (this.ranks[groupsX] > this.ranks[groupsY]) {
      this.groups[groupsY] = groupsX;
    } else if (this.ranks[groupsX] < this.ranks[groupsY]) {
      this.groups[groupsX] = groupsY;
    } else {
      this.groups[groupsY] = groupsX;
      this.ranks[groupsX] += 1;
    }

    return true;
  }
}