All problems

Storm Over the Hub

Hard · graph traversal

An airline serves n airports, numbered 0 to n - 1. Each entry of flights is [a, b]: a route that joins airport a and airport b, flown in both directions.

A region is a group of airports that can be reached from one another, directly or by changing planes at other airports in the group, with no route to any airport outside the group. An airport with no routes at all is a region on its own.

A storm is about to close exactly one airport. The closed airport disappears completely, together with every route that touches it, and it does not count as part of any region. Only the other n - 1 airports are left, and they fall into some number of regions.

Choose the airport to close so that the number of regions left is as large as possible. Return [airport, regions]: the airport you chose and the number of regions that remain. If several airports give the same largest number, choose the one with the smallest number.

If n is 1, closing the only airport leaves nothing, so return [0, 0].

Examples

Example 1

Input: n = 5, flights = [[0, 1], [1, 2], [1, 3], [3, 4]]

Output: [1, 3]

Closing airport 1 leaves {0}, {2} and {3, 4}: three regions. No other airport does better; closing 3 leaves two.

Example 2

Input: n = 3, flights = [[0, 1], [1, 2], [2, 0]]

Output: [0, 1]

Whichever airport closes, the other two are still joined by a route, so one region remains. All three tie, so airport 0 is chosen.

Example 3

Input: n = 4, flights = [[0, 1]]

Output: [0, 3]

Airports 2 and 3 are on their own. Closing 0 leaves {1}, {2} and {3}: three regions. Closing 1 also leaves three, but 0 is the smaller number.

Constraints