Answer repeated reachability queries on a graph after edges are added or processed in a specific order.
Problem
You are given an undirected graph with n vertices labeled from 0 to n - 1. You also have a list of path-existence queries. Each query asks whether two vertices are connected in the graph.
In this version of the problem, the graph is not meant to be searched from scratch for every query. Instead, the key is to process connectivity efficiently using a disjoint set structure or another offline approach.
For each query [u, v], determine whether there exists a path between u and v in the graph.
Return the result for every query in order.
Notes
- The graph is undirected.
- A path may use any number of edges.
- A vertex is always connected to itself.
Input Format
n: number of vertices.edges: list of undirected edges, where each edge is represented as a pair[u, v].queries: list of query pairs[u, v].
For each query, check whether u and v belong to the same connected component.
Output Format
- Return a boolean array where the
i-th value istrueif the two vertices in thei-th query are connected, andfalseotherwise.
Constraints
1 <= n0 <= u, v < nedgesandqueriescontain valid vertex indices.- Multiple queries should be answered efficiently.
- The graph may contain duplicate edges.
Example 1
Input
n = 4 edges = [[0,1],[1,2]] queries = [[0,2],[0,3],[1,1]]
Output
[true,false,true]
Explanation
- 0 and 2 are connected through 1.
- 0 and 3 are in different components.
- Any vertex is connected to itself.
Example 2
Input
n = 5 edges = [[0,1],[2,3],[3,4]] queries = [[0,1],[1,2],[2,4]]
Output
[true,false,true]
Explanation
- 0 and 1 are directly connected.
- 1 is not connected to 2.
- 2 connects to 4 through 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.