Overview

This is a simulation problem on a directed graph where substations whose load (in-degree) exceeds their durability experience a blackout, and the blackout propagates in a chain reaction. We use BFS (Breadth-First Search) to efficiently simulate the cascading blackouts.

Analysis

Understanding the Problem Structure

The initial load of each substation \(i\) is its “in-degree” (the number of power lines coming into it). A substation whose load strictly exceeds its durability \(T_i\) experiences a blackout.

For a substation \(s\) that experiences a blackout, the load of each substation at the end of an outgoing edge (power line going out from \(s\)) increases by \(1\). This models the scenario where “since the power supply from \(s\) has been cut off, the destination substations try to compensate from other sources, causing their load to increase.”

Key Observations

• The chain of blackouts has a domino effect structure. One blackout increases the load on surrounding substations, triggering new blackouts.
• The problem statement guarantees that “the final result is the same regardless of the order of processing.” This ensures that a queue-based approach like BFS produces the correct result.
• Naively “scanning all substations each time to find those meeting the condition” could lead to \(O(N^2)\) complexity, but using a queue ensures each substation is processed at most once, making it efficient.

Understanding Through a Concrete Example

For example, suppose there are power lines \(A \to B \to C\), where \(B\) has in-degree \(1\) and durability \(0\).

1. \(B\)’s initial load is \(1 > 0 = T_B\), so it blacks out.
2. Since there is a power line from \(B\) to \(C\), \(C\)’s load increases by \(+1\).
3. If \(C\)’s load exceeds its durability, \(C\) also blacks out… and the chain continues.

Algorithm

1. Initialization: Calculate the in-degree of each substation and use it as the initial load.
2. Initial Queue Insertion: Add all substations where load \(>\) durability to the queue and set their blackout flag.
3. BFS Loop:
   • Dequeue a substation \(s\).
   • Examine all outgoing edges of \(s\). For each destination \(v\) that has not yet blacked out, increase \(v\)’s load by \(+1\).
   • If \(v\)’s load exceeds its durability, set its blackout flag and add it to the queue.
4. Output: Once the queue is empty, output the blacked-out substations in ascending order. If there are none, output -1.

The key point is that the blackout flag is set at the time of queue insertion. This prevents the same substation from being added to the queue multiple times.

Complexity

• Time complexity: \(O(N + M)\)
  • Each substation enters the queue at most once, and each power line is traversed at most once when the source substation is processed.
• Space complexity: \(O(N + M)\)
  • Required for the adjacency list, load array, blackout flag array, etc.

Implementation Notes

• Fast Input Reading: Since \(N, M\) can be up to \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.buffer.read().

• Blackout Flag Management: By setting blacked_out[v] = True at the time of adding to the queue, we prevent the same substation from entering the queue multiple times. Adding to the queue every time the load increases would cause unnecessary processing.

• Load Invariance: The problem states that “the load of a substation that has already blacked out does not change thereafter,” so we should not increase the load of substations where blacked_out[v] is True.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        T[i] = int(input_data[idx]); idx += 1
    
    # out_edges[u] = list of v such that there's an edge u -> v
    out_edges = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        out_edges[u].append(v)
        in_degree[v] += 1
    
    # load[i] starts as in_degree[i]
    load = [0] * (N + 1)
    for i in range(1, N + 1):
        load[i] = in_degree[i]
    
    # BFS/queue-based simulation
    blacked_out = [False] * (N + 1)
    queue = deque()
    
    for i in range(1, N + 1):
        if load[i] > T[i]:
            queue.append(i)
            blacked_out[i] = True
    
    result = []
    
    while queue:
        s = queue.popleft()
        result.append(s)
        # For each outgoing edge from s
        for v in out_edges[s]:
            if not blacked_out[v]:
                load[v] += 1
                if load[v] > T[v]:
                    blacked_out[v] = True
                    queue.append(v)
    
    if not result:
        print(-1)
    else:
        result.sort()
        print(' '.join(map(str, result)))

main()

---

This editorial was generated by claude4.6opus-thinking.