Same Network Queries
A radio network has n stations numbered 0 to n - 1. links is a list of pairs [a, b]: stations a and b can talk to each other directly. The same pair may appear more than once, and a may equal b. Two stations are in the same network when a message can travel from one to the other over zero or more links, so a station is always in the same network as itself.
queries is a list of pairs [x, y]. Return a list of booleans, one per query in order: true when x and y are in the same network and false otherwise. Return [] when queries is empty.
Example 1
Stations 0 and 2 are joined through 1; station 3 has no link; 3 is in the same network as itself.
Example 2
There are no links, so only a station and itself share a network.
Constraints
1 <= n <= 500 <= len(links) <= 1000 <= len(queries) <= 500 <= a, b, x, y <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Tunnels to Every StationEasy
- Blocks to the Nearest ShopMedium
- Build Order ExistsMedium
- Calm SquaresMedium
- Cheapest Toll TripMedium
- Connect All OfficesMedium
- Count the Shortest RoutesMedium
- Forced SidesMedium