In DENSEGRAPH problem, is the weights from each ui to each vi or is it a single ui to all v? Please reply fast
each ui to each vi, in ranges given.
[1, 2, 3] to [4, 5]
means 1 → 4, 1 → 5, 2 → 4, 2->5, 3->4, 3->5
Why does a simple BFS give wrong answer?
BFS will work but needs modification since we have ranges. And each range will overlap with some set of ranges, so given if we are at some range, We have to find all ranges that overlap with range we are at, and then we can go to all ranges that we can reach from all the ranges overlapping with this range.
lets say: we are in [2, 3]
and [1, 3] → [10, 20]
[2, 4] → [15, 16]
so from [2, 3] we can go to [10, 20] and [15, 16].
We can create multiple nodes for overlap. Suppose, ranges are [1,10], [5,15]
It will be good to make 3 nodes [1,5], [5,10], [10,15]
Will make search over BFS easier as you don’t need complicated modifications in BFS now.
I don’t know, but I think that maybe this can lead to lots of segmented ranges, and probably make it complicated.
1 Like