Power Grid Maintenance ⚡️

Difficulty: Medium

Topics: graphs, disjoint-set (union-find), queries
Hint: Efficiently track connected components and the smallest operational node in each component.

Problem Statement

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] = [u_i, v_i] indicates a connection between station u_i and station 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 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 (answer = x).
  • 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: Taking a node offline does not change connectivity — it remains part of its grid for component membership.

Examples

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 in one grid.
• [1,3] → station 3 is online → returns 3.
• [2,1] → station 1 goes offline.
• [1,1] → station 1 offline → smallest online in its grid is 2 → returns 2.
• [2,2] → station 2 goes offline.
• [1,2] → station 2 offline → smallest online in its grid is 3 → returns 3.

Example 2

Input:
{
  "c": 3,
  "connections": [],
  "queries": [[1,1],[2,1],[1,1]]
}

Output: [1, -1]

Explanation

• No connections → each station is its own grid.
• After station 1 goes offline, querying it returns -1 because no other operational station exists in its grid.

Constraints (important)

🧮 Time & Space Complexity

Time Complexity

• DSU Build: O((c + n) × α(c))
• TreeSet Operations: O(log c)
• Overall: O((c + n + q) × log c)

Space Complexity

• DSU + Online Flags + TreeSets: O(c)

✅ Efficient and near-optimal for up to 10⁵–2×10⁵ inputs.