Given an undirected weighted graph G, with N nodes and E edges. You have to answer Q queries.
In each query, you are given two nodes u and v. The answer to the query is the minimum value k such that there is a path from node u to node v such that the maximum weight of the edge in path is at most k.
Constraints : N,E,Q <= 10^5
Can anyone please explain me how to solve this problem!
My guesses at solving this:
In both proposed solutions, store the max(u, v) value for each edge. We need to iterate edges in this order like Kruskal's.
Method 1: Store a DSU data structure. Store an array of arrays arr where for each node, store the query numbers involving the node. Iterate the edges in increasing order of max(u, v). If u and v have different DSU parents, merge them. Merge the smaller arr size to larger arr size. If there are common elements, the ans[common query number] = max(u, v), and exclude the common elements from the new array.
Method 2: form a minimal spanning tree using Kruskal's. Construct 2 binary lifting array of arrays, one storing the power of 2 ancestors and the other storing the max node values in the power of 2 ancestors. Finally, for each query, find the LCA and get the max(u to LCA, v to LCA).
Both solutions should run in O(nlogn). Not 100% sure about the correctness though.
A simpler way is to add vertices in increasing order of weight and doing small to large merging with query indices stored in components. Not sure why you used edge weights.
Cool. Yours is a better way. I recommended dealing with edges because I thought of the problem as testing the understanding of Kruskal's MST, and wanted to incrementally add the edges. But adding nodes in increasing order will require fewer lines of code and is cleaner so that's a better approach.
Ah, that makes sense. Also, is there a way to do the merging in $$$O(n \log n)$$$ without hashsets? I can only get an $$$O(n \log^2 n)$$$ solution where the small to large merging requires about $$$O(n \log n)$$$ operations, each of which cost roughly $$$O(\log n)$$$.
I will use hashsets (I primarily use Python and Python sets run fairly fast, even faster than C++ unordered_set if I'm not mistaken).
However, if you really want to avoid hashsets and maintaining O(nlogn) complexity, then you can use a linked list for each node, storing the query index in ascending order (also store the size of the linked list). At the start, populate the linked lists by iterating in increasing order of the query index. While merging, use two-pointers over the 2 linked lists (much like merge-sort) to merge/answer queries.
The issue with merging like this is that it doesn't seem like you can merge the smaller list into the larger list in $$$O(\min(n, m))$$$ time (and I can only do this in $$$O(n + m)$$$ time).
Oh yes you're right. Both linked lists are iterated through in the worse case. To make use of small-to-large merging's advantage, only the smaller set can be iterated through. Then I guess that a hashset would be the best bet in terms of time complexity. If the hashing algorithm has too much overheads and you're not satisfied with the treeset/ordered set's additional logn factor, then perhaps binary lifting over the MST is the next suitable option.
What do you mean by "with query indices stored in components."? can you explain plzz
Let's say for node 1 you have queries [1,2] and node 2 you have nodes [1,3,4,5]. If you union nodes 1 and 2 (due to edge 1-2 being the next edge having minimum max(a[1],a[2]), then you get a new component. Make ans[query1]=max(a[1],a[2]) and queries[par[1]]=[2,3,4,5]. Note that after union, par[1]=par[2]. The query indices stored in component [1,2] are [2,3,4,5]. Do use sets instead of arrays for small time complexity.
Thanks for sharing YMSeah
I implemented the solution in JAVA using method 2.
Code :
The hiring challenge is going on. Please don't post these kinds of questions before the challenge is completed. https://assessment.hackerearth.com/challenges/hiring/beaconstac-winter-internship-challenge-2022/
Exact same problem https://lightoj.com/problem/a-secret-mission