It was asked to my friend in google coding challenge and I'm unable to think of any approach.
Can anyone help?
Given a weighted undirected graph G that contains N nodes and M edges.
Each edge has a weight w associated with it.
Answer Q queries:
- x y W : Find if there exists a path between node x and node y such that the maximum weight on that path doesn't exceed W. If it exists print 1 or else print 0.
1<=T<=5
1<=N,M,Q,W,w<=10^5
1<=x,y<=N
Offline approach: Maintain a dsu and add edges in increasing order of weight. Also maintain the answer for each query(ie if x and y are connected) when its weight comes in the order.
I couldn't understand, can you explain please?
Initially you have empty graph (without edges). Sort edges and queries together by weight (in case of equal weights, edges come first). Iterate through this array: when it's edge, just connect vertices in DSU (disjoint-set-union), when it's query, check if vertices are connected in DSU.
Ohh, now I get it! Thanks a lot for explaining.
You can consider the weight of edges greater than W as 1 and 0 otherwise. Then you can use DSU on vertices connected to edges with weight 0. if x and y belong to the same group answer is 1 else 0.
W varies with Queries.
link, Code if needed
Thanks :)
In the minimum spanning tree path between any two vertices $$$s$$$ and $$$t$$$ has minimum maximum edge over all $$$s$$$-$$$t$$$-paths in the original graph.
Thus, you can build MST and then answer maximum on path queries (using binary lifting) to check if maximum doesn't exceed $$$W$$$.
Pedantic nitpick: The graph may be disconnected, so you may end up with a spanning forest instead of a tree. Of course, there are several easy ways to work around this: Probably the simplest is to add fictitious edges with weight greater than the maximum allowed query weight to pretend the graph is connected.
Yes, I initially thought of this approach. I was not sure about "In the minimum spanning tree path between any two vertices s and t has minimum maximum edge over all s-t-paths in the original graph." though.
Then because it was a coding interview problem , I thought it should have a simpler solution.