Hi everyone,
Recently I discovered Boruvka's Algorithm and I think this algorithm is really interesting. So I made a video lecture on this algorithm where I cover 2 problems related to it (1 standard and 1 relatively hard).
I hope that you will enjoy this video and learn something new. I worked very hard editing and making this video for 2 days, so make sure to subscribe to my channel and like the video :)
Here's the video click.
Comments:
I'm still working on the 2nd part of this video lecture where I'm explaining this problem CF 888G. As soon as this part will be ready, I will upload the video, so don't miss it.
Problems from the lecture
Problems from the readers
UPD:
Any feedback is appreciated a lot. If you have any algorithms/concepts/tricks which you would like to see in the next videos, feel free to let me know in the comments below.
Thank you!
Great job, go on!
Nice job, keep it up mate!
One more problem. 1305G
Thanks for the suggestion
NotIdeal, CMaster thanks :D
Nice video. my question is not related to the algorithm but can we use DSU without union by rank or other technique in contest problems?
As I know in most cases it's sufficient just to use path compression without any heuristics.
Path compression:
Without path compression:
I know a data structure which stores components in a vector, and when you merge two components, you just add one vector after another (with a little trick) and it works in nlogn and it's really simple
Yes, it's called small to large technique, which you can use as well :)
Didn't know it's name, thank you!
Your explanation is excellent and easy to understand. Keep it up!
I'm very happy that you liked the video, thanks a lot!
Please post if any question related to this is on any platform.
Thanks, done!
Keep it up !
I'll try my best!
Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).
Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).
Note that the given implementation of Boruvka is in $$$O(m\log(n)^2)$$$ and not $$$O(m\log(n))$$$. A typical implementation of Boruvka does not use DSU.
As I know using path compression gives in total $$$m * log(n) $$$ operations, which means that my code's time complexity is $$$O(m * log(n)) $$$.
Don't get me wrong, when I was describing Boruvka's algorithm I didn't claim that it needs to be used with DSU. Also I mentioned that it's also possible to use heuristics to make DSU faster, but it's sufficient not to use heuristics.
I think your solution must be interesting, could you please explain how would you approach Boruvka's algorithm without DSU?
your solution needs $$$\log(n)$$$ phases for each phase you iterate over all $$$m$$$ edges and check if the head and tail are in the same component which requires $$$\log(n)$$$ operations since you used a DSU to do this. This results in a total time of $$$O(m\log(n)^2)$$$.
A normal Boruvka implementation marks all local minimal edges $$$O(m)$$$ (Note that you need a tie-breaking for edges with equal weight since the local edges else could form a circle). Then a DFS is used to find a spanning forest which only uses marked edges $$$O(m)$$$ (this forest will be part of our MST). Each component in the forest gets an id. Then all edges $$$(a,b)$$$ will be changed to $$$(id(a), id(b))$$$ in $$$O(m)$$$ (selfloops can be removed). And we begin from start with those new edges until there are no remaining edges.
The total runtime for one phase thus is $$$O(m)$$$ whereas your implementation requires $$$O(m\log(n))$$$ steps per phase.
Your idea is quite interesting, but personally for me it's more convenient to use DSU.
This claim
"which requires log(n) operations since you used a DSU to do this"
is not really true, because if I'm not missing anything, DSU only with path compression does at most $$$m * log(n)$$$ operations in total, approximately after that many operations each call of $$$root(v)$$$ would work in $$$O(1)$$$well it takes at most $$$m\log(n)$$$ operations for $$$m$$$ calls and it will eventually be in $$$O(1)$$$... But this does not imply that after doing any kind of $$$m$$$ calls the following calls will be in $$$O(1)$$$. And we don't do $$$m$$$ calls, we actually do $$$m\log(n)$$$ calls. Therefore I am not sure about the complexity... (It could still be true but I am not sure and a basic analysis only results in $$$O(m\log(n)^2)$$$)
My implementation would look like this:
I think the crucial point is that we don't have $$$m * log(n)$$$ different edges, we do have only $$$m$$$. Anyways, let's not argue on the time complexity :D
Thank you for the nice implementation. It's very useful.
https://www.codechef.com/problems/SPANTREE
I would recommend trying this problem before watching the video to truly appreciate (perhaps self-discover) the algorithm :)
Yeah, it's really fascinating when you discover a new algorithm even not knowing it exists already :D
Thank you for the new problem.
Hey, thank you for the tutorial. This is a really well-made one. Explanations are very clear and understandable. The only suggestion from me would be to increase your volume a bit.
Expecting more tutorials from you. Good luck!
Sorry if the audio wasn’t that brilliant, I’ll try my best to make audio much much better in the next videos.
I’m very glad you liked it :)
best video for boruvka, I have seen this problem before but didn't understand shit, thanks for making video on it,this is the problem Gaussian problem, hope you could make tutorial on it explaining Gaussian elimination in gf(2) i.e. modulo 2, it is a great concept and do not have any good tutorial to explain.
I'll add the Gaussian elimination into my list of algorithms to cover. Thanks for suggestion ;)
Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).