pritishn's blog

Help needed in a graph path query problem.
By pritishn, 4 years ago, In English

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

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Ohh, now I get it! Thanks a lot for explaining.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply