CODEWITHSUNDEEP
algorithmgraph-theoryundirected-graph
prakasht
prakasht

Reputation: 478

Find maximal weight edge between two nodes in an undirected acyclic graph

We have a graph with N nodes and N-1 bidirectional edges(each edge has some weight w). Now we have to answer q number of queries. Each query gives two nodes u and v and maximum allowed cost at any edge x. If the individual edge weights of all edges between path from u to v is less than or equal to x, then we print Yes otherwise we print No.

The constraints are as follows:
1 ≤ N,q ≤ 10^6
1 ≤ w,x ≤ 10^9

I have tried the brute force solution but it gives TLE. I know I have to do some preprocessing but can't get my head over it. I found a similar question here but no one clearly addressed that part.
Maximum edge weight from one node A to node B.
You can visit the link for better explanation of the problem.

Upvotes: 0

Views: 1215

Answers (1)

Photon
Photon

Reputation: 2777

This can be easilly solved using Union Find (also known as Diesjoint Set Union, if never heard about it you can look up implementation here) data structure in O(nlog(n) + qlog(q))

  1. Read all queries and store them in some array structure (keeping query info u v x and index of query)

  2. Sort all queries by weight

  3. Sort all edges by weight

  4. Go throught all queries, if needed merge all still unmerged edges with weight <= query weight

  5. If nodes u and v are in same connected component (Find(u)==Find(v)) then answer for this querie is Yes else no

  6. Print answers in needed order

Upvotes: 3

Related Questions