FunctionRacerProblemsRace

Same Network Queries

EasyGraphsPython, JavaScript, TypeScript, Java, C++

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

n 5
links [[0,1],[1,2]]
queries [[0,2],[2,3],[3,3]]
returns [true,false,true]

Stations 0 and 2 are joined through 1; station 3 has no link; 3 is in the same network as itself.

Example 2

n 3
links []
queries [[0,1],[2,2]]
returns [false,true]

There are no links, so only a station and itself share a network.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems