Ski Lodge Closure Impact
Count newly disconnected node pairs after each node removal in a graph
A ski resort has n lodges numbered from 0 to n - 1. Its two-way snow corridors are given by corridors, where each entry [a, b] connects lodges a and b. Multiple corridors may connect the same pair of lodges, and the resort need not be connected.
The patrol is evaluating the impact of closing each lodge independently. Closing lodge v removes that lodge and every corridor incident to it. All other lodges and corridors remain available.
For each lodge v, count the unordered pairs of other lodges {a, b} that:
- could reach one another before the closure, and
- cannot reach one another after lodge
vis closed.
Neither endpoint of a counted pair may be the closed lodge. Pairs that were already disconnected do not count.
Return an integer array of length n, with the count for closing lodge v at index v.
Examples
Example 1
Input: n = 5, corridors = [[0,1],[1,2],[1,3],[3,4]] Output: [0,5,0,3,0]
The corridors form a branching tree. Closing lodge 1 separates its neighboring branches, while closing lodge 3 separates lodge 4 from the rest. Closing a leaf does not separate any pair of surviving lodges.
Example 2
Input: n = 5, corridors = [[0,1],[1,2],[2,0],[2,3]] Output: [0,0,2,0,0]
Lodges 0, 1, and 2 form a loop, with a corridor from lodge 2 to lodge 3. The loop offers an alternate route when one of its corridors is unavailable, but closing the lodge that attaches lodge 3 can still disconnect surviving lodges. Lodge 4 is already isolated and does not contribute to newly disconnected pairs.
Example 3
Input: n = 1, corridors = [] Output: [0]
The resort contains only one lodge. There are no pairs of other lodges to evaluate.
Constraints
- 1 <= n <= 3500
- 0 <= corridors.length <= 3500
- Each corridor has exactly two integer endpoints in the range [0, n - 1].
- A corridor's endpoints are distinct.
- Multiple corridors between the same two lodges are allowed.
Each closure is evaluated against the original resort, not after any previous closure. An iterative traversal avoids dependence on the language's recursion limit. The intended complexity is O(n + corridors.length) time and space.
Hints
Show hint 1Hint 1
During a depth-first traversal, determine which child subtrees cannot reach an ancestor of their parent without passing through that parent. Identify corridors by their input indices so parallel corridors are handled correctly.
Show hint 2Hint 2
After removing a lodge, its original connected component splits into several groups. Count pairs across those groups using their sizes, including the group containing the lodge's ancestors.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you compute the number of newly disconnected lodge pairs caused by closing each individual corridor instead?
- If each lodge housed a different number of guests, how would you count newly disconnected pairs of guests while excluding guests at the closed lodge?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem