Same Cluster Queries
EasyGraphs
Problem
A data centre has n servers numbered 0 to n - 1. Each entry [a, b] of links is a two-way cable between servers a and b.
An operator asks many questions at once: each entry [x, y] of queries asks whether servers x and y can reach each other through cables. Return an array of booleans, one answer per query, in order. A server can always reach itself.
Example 1
- Input:
- n = 5, links = [[0, 1], [1, 2], [3, 4]], queries = [[0, 2], [0, 3], [4, 3]]
- Output:
- [true, false, true]
{0, 1, 2} and {3, 4} are separate clusters.
Example 2
- Input:
- n = 3, links = [], queries = [[0, 0], [0, 1]]
- Output:
- [true, false]
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ links.length ≤ 10^5
- 0 ≤ queries.length ≤ 10^5
- All server numbers are in [0, n).
Hint
Show the first hint
Running a search for every query repeats the same work. What could you compute once and reuse?
Walkthrough
How to approach it
01Clarify before coding
- Can links and queries be interleaved? No: all links exist before any query, so answers are static.
- Is a query [x, x] valid? Yes, and the answer is true.
- Can there be many more queries than servers? Yes, up to 10^5 of each, so per-query work must be tiny.
02Brute force
For each query, run a BFS from x and check whether y is reached.
Cost: O(q · (n + m)): about 2·10^10 steps with 10^5 queries on a large network.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.