After a storm, the main grid is down. Houses 0 .. n-1 are linked by private cables that still work, and a house has power if it can reach any house with a working backup generator through a chain of cables (cables carry power both ways). The utility wants an outage report: for every group of connected houses that has no generator at all, how many houses are in it?
Write outage_report(n, cables, generators) -> list[int]:
cablesis a list of pairs(a, b), each an undirected cable between housesaandb. Cables may repeat, and a self-loop(a, a)may appear.generatorsis a list of houses that have a generator (it may contain repeats, and may be empty).- Return the sizes of the dark groups, largest first. A house with no cables and no generator is a dark group of size 1. If every house has power, return
[].
outage_report(8, [(0, 1), (1, 2), (3, 4), (5, 6)], [4])
# [3, 2, 1]
# groups: {0,1,2} dark, {3,4} powered by 4, {5,6} dark, {7} dark
outage_report(3, [(0, 1), (1, 2)], [2])
# []
Constraints: 1 <= n <= 10**5, up to 2 * 10**5 cables. One test is a single street of 50,000 houses in a line, far past Python's recursion limit, so walk the graph with an explicit stack (or raise the limit carefully).
Show hint
build an adjacency list, then loop over every house; each time you meet an unvisited one, flood its whole group with a stack while counting its size and noting whether any member has a generator (a set makes that check O(1)).