Show problems as
Classic problem #3607MediumArrayHash TableDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryHeap (Priority Queue)Ordered Set

Power Grid Maintenance

Real-world version: The Lowest Working Well in the Cluster
Tracked in this browser only
Read Power Grid Maintenance on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A farm draws from count wells numbered 1 through count, and pipes lists the pairs of wells a pipe joins. Two wells belong to the same cluster when a chain of pipes runs from one to the other, so a well with no pipes is a cluster on its own. Every well is working to begin with.

Work through orders in turn. An order comes in one of two kinds:

  • [1, well] calls for water at that well. If the well is working the answer is that well itself. Otherwise the answer is the lowest-numbered working well of its cluster, and -1 when its cluster has none working.
  • [2, well] takes that well out of service. A well already out of service is left as it is, and a well out of service never comes back.

Return the answers to the [1, well] orders, in the order they were called.

Examples

Example 1

Input
count = 4, pipes = [[1, 2], [3, 4]], orders = [[1, 1], [2, 1], [1, 1], [1, 3], [2, 3], [1, 3], [2, 4], [1, 4]]
Output
[1, 2, 3, 4, -1]

Two clusters, wells 1 and 2 in one and wells 3 and 4 in the other. The first call finds well 1 working. Once it goes out of service the same call falls back on well 2, its only clustermate. Wells 3 and 4 go the same way, and the last call comes after both have gone, so nothing is left in that cluster.

Example 2

Input
count = 5, pipes = [[1, 2], [2, 3], [4, 5]], orders = [[2, 2], [1, 2], [2, 1], [1, 2], [2, 3], [1, 1], [1, 5]]
Output
[1, 3, -1, 5]

Wells 1, 2 and 3 share a cluster. With well 2 out of service the call at it falls back on well 1, and once well 1 has gone too the same call falls back on well 3. After well 3 goes the cluster is empty, while well 5 in the other cluster is untouched and answers itself.

Example 3

Input
count = 5, pipes = [], orders = [[2, 3], [1, 3], [2, 5], [1, 5], [1, 4]]
Output
[-1, -1, 4]

No pipes at all, so every well stands alone. A call at a well out of service has nowhere to fall back on, while well 4 is still working and answers itself.

Constraints

  • 1 <= count <= 10^5
  • 0 <= pipes.length <= 10^5
  • 1 <= orders.length <= 2 * 10^5
  • pipes[i].length == 2
  • orders[i].length == 2
  • pipes[i] joins two different wells, each numbered from 1 to count
  • each orders[i] reads [1, well] or [2, well], with well numbered from 1 to count

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def process_queries(count: int, pipes: list[list[int]], orders: list[list[int]]) -> list[int]:
Java
public int[] processQueries(int count, int[][] pipes, int[][] orders)

More on the same topics