Solution

Method 1 – Offline Union-Find with Query Sorting

Intuition

For each query, we want to know if there is a path between two nodes such that all edge weights are strictly less than a given limit. By sorting both the edges and the queries by weight/limit, we can use a union-find (DSU) structure to incrementally connect nodes as the limit increases, efficiently answering all queries.

Reasoning

By processing queries in order of increasing limit, and always adding all edges with weight less than the current limit to the union-find, we ensure that at each query, the union-find structure represents the connectivity for all edges with weight less than the limit. Thus, we can answer each query in nearly constant time after sorting.

Approach

Store all edges and queries, and sort both by edge weight and query limit, respectively.
Use a union-find (DSU) structure to keep track of connected components.
For each query (in order of increasing limit):
- Add all edges with weight less than the query's limit to the union-find.
- Check if the two nodes in the query are connected in the union-find.
Return the answer for each query.

Edge cases:

No edges: only nodes themselves are connected.
Multiple edges between nodes: only the smallest matters for each limit.

Code

[{"language":"Java","code":"class DistanceLimitedPathsExist {\n    int[] par;\n    int[] rank;\n    List<int[]> edges;\n    public DistanceLimitedPathsExist(int n, int[][] edgeList) {\n        par = new int[n];\n        rank = new int[n];\n        for (int i = 0; i < n; i++) par[i] = i;\n        edges = new ArrayList<>();\n        for (int[] e : edgeList) edges.add(e);\n        edges.sort(Comparator.comparingInt(a -> a[2]));\n    }\n    int find(int x) {\n        if (par[x] != x) par[x] = find(par[x]);\n        return par[x];\n    }\n    void union(int x, int y) {\n        int px = find(x), py = find(y);\n        if (px == py) return;\n        if (rank[px] < rank[py]) par[px] = py;\n        else if (rank[px] > rank[py]) par[py] = px;\n        else { par[py] = px; rank[px]++; }\n    }\n    int idx = 0;\n    public boolean query(int p, int q, int limit) {\n        while (idx < edges.size() && edges.get(idx)[2] < limit) {\n            union(edges.get(idx)[0], edges.get(idx)[1]);\n            idx++;\n        }\n        return find(p) == find(q);\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> DistanceLimitedPathsExist</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></spa

Related Tags