problem link
my code
i have used disjoint set union approach and hae coded till there plz tell me how to proceed from there and get the required output…
add that part of code in my code…
plz reply fast…
Roads in hackerland
Plz reply as Early as possible
why is no ta replying to this doubt …
plz tell…its been 4days since i have posted it…
hey, @S19LPPP0202
can u tell me your thought behind using this logic
i personally feel this problem could be directly tackled using the floyd warshall algorithm
I have built a minimum spanning tree and then want to find dist between all pairs …so tell me how to do that …in my code i have done till building the minimum spanning tree tell me how to iterate over all pairs…
I want to solve this problem in this Manmer only…plz reply along with propper change in my code…
Its been 6 days since i have posted it
Plz reply at the earliest at least now…
in making a mst, u will lose a lot of valid pairs of shortest path
when there are cycles or the shortest path from one node to another is greater than the shortest path to another node, u will be losing a lot of optimum paths
Ok but if after creating a mst i want to find the dist bw each pair of nodes(cities) how would i do that …provide the code for that traversal…
Provide the code along with explaination
Reply at the earliest along with code…
you want to be able to answer queries of form distance(u, v) fast enough with fast preprocessing, you may use LCA. LCA, or lowest common ancestor, of two vertices in a rooted tree is a vertex which is an ancestor of both of them and which is the lowest among all of theirs common ancestors. There is a not very complex algorithm to find LCA(u, v) in logarithmic time with n log n preprocessing time. I can describe it if it is needed.
So, your problem may be solved as following. First, fix a root of your tree. Then make an above mentioned preprocessing to be able to find LCA. Then, supposing h[v] is a distance from v to the root (can be precomputed in linear time for all vertices) then distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)].
Also refer to this
Plz provide its code as well the LCA approach
PLZ REPLY AT LEAST…
hey, i provided the approach
this si for the LCA
supposing h[v] is a distance from v to the root (can be precomputed in linear time for all vertices) then distance(u, v) = h[u] + h[v] - 2 * h[LCA(u, v)].
just modify it using this formula, and you will be able to solve