Need help with a Graph Question (Walmart SDE Intern Test)

help
,
1

The test was conducted a couple of days back, any help is appreciated. The only thing that I could think of was to mark the edges as -1 and to not traverse them but that’d be O(n*m).

1
11152×864 63.7 KB

See the given example :
https://ibb.co/7bXymcF

2

You need to traverse in a reverse manner. Start from the state where there are no roads. The inconvenience would be n*(n-1).
Now when you keep adding roads, use dsu to find the sizes of the connected components you are joining with the road. If the road is within the same component you are not joining any additional cities because all of the cities in that component were already connected. Else if you are joining components of size c1 and c2 you need to subtract c1*c2 from the previous inconvenience because now after adding the road both these components were connected and thus we need to subtract their inconvenience.

3

Thanks got it completely :slight_smile:

1 Like