Answer multiple path-existence queries on a graph efficiently.
Path Existence Queries in a Graph I
gfgProblem
You are given an undirected graph with n vertices labeled from 0 to n - 1. The graph contains a set of edges, and you must answer a list of queries. Each query asks whether there is a path between two given vertices.
For every query [u, v], determine whether u and v belong to the same connected component in the graph.
Return an array of boolean values where each value corresponds to one query.
Intuition
Because the graph is undirected, path existence depends only on connected components. Once the components are known, each query can be answered quickly.
Input Format
n: number of vertices.edges: list of undirected edges, where each edge is a pair[u, v].queries: list of pairs[u, v]to test for connectivity.
Output Format
- Return a boolean array
ans. ans[i]istrueif there exists a path between the endpoints ofqueries[i], otherwisefalse.
Constraints
- Vertices are labeled from
0ton - 1. - Edges are undirected.
- Queries ask about connectivity between two vertices.
- Use an approach that supports answering many queries efficiently.
Example 1
Input
n = 5 edges = [[0,1],[1,2],[3,4]] queries = [[0,2],[0,3],[3,4],[1,4]]
Output
[true,false,true,false]
Explanation
Vertices 0, 1, and 2 are connected, and vertices 3 and 4 are connected. So 0 and 2 are reachable, 0 and 3 are not, 3 and 4 are reachable, and 1 and 4 are not.
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.