### RockyB's blog

By RockyB, history, 4 years ago,

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.

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

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!

• +218

 » 4 years ago, # |   +14 Great job, go on!
 » 4 years ago, # |   +16 Nice job, keep it up mate!
 » 4 years ago, # |   +7 One more problem. 1305G
•  » » 4 years ago, # ^ |   +12 Thanks for the suggestion
 » 4 years ago, # |   +3 NotIdeal, CMaster thanks :D
 » 4 years ago, # |   0 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?
•  » » 4 years ago, # ^ |   0 As I know in most cases it's sufficient just to use path compression without any heuristics. Path compression: int root(int v) { if (p[v] == v) return v; return p[v] = root(p[v]); } Without path compression: int root(int v) { if (p[v] == v) return v; return root(p[v]); } 
•  » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ |   +3 Yes, it's called small to large technique, which you can use as well :)
•  » » » » 4 years ago, # ^ |   0 Didn't know it's name, thank you!
 » 4 years ago, # |   +3 Your explanation is excellent and easy to understand. Keep it up!
•  » » 4 years ago, # ^ |   0 I'm very happy that you liked the video, thanks a lot!
 » 4 years ago, # |   0 Please post if any question related to this is on any platform.
•  » » 4 years ago, # ^ |   0 Thanks, done!
 » 4 years ago, # |   +8 Keep it up !
•  » » 4 years ago, # ^ |   +3 I'll try my best!
 » 4 years ago, # |   0 Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).
 » 4 years ago, # |   +3 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 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?
•  » » » 4 years ago, # ^ |   +3 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.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +3 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)$
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +3 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: struct edge { ll a, b, w, id; bool operator<(const edge& o) const { if (w != o.w) return w < o.w; return id < o.id; } }; vector boruvka(ll n, vector edges) { vector res(edges.size()); while (!edges.empty()) { //find local minimal edges vector minEdge(n, -1); for (ll i = 0; i < edges.size(); i++) { if (minEdge[edges[i].a] < 0 || edges[i] < edges[minEdge[edges[i].a]]) minEdge[edges[i].a] = i; if (minEdge[edges[i].b] < 0 || edges[i] < edges[minEdge[edges[i].b]]) minEdge[edges[i].b] = i; } //build graph with local minimal edges vector> adj(n); for (ll x : minEdge) { if (x < 0) continue; res[edges[x].id] = true; adj[edges[x].a].push_back(edges[x].b); adj[edges[x].b].push_back(edges[x].a); } //find components vector c(n, -1); ll cs = 0; for (ll i = 0; i < n; i++) { if (c[i] >= 0) continue; vector s = {i}; c[i] = cs; while (!s.empty()) { ll x = s.back(); s.pop_back(); for (ll y : adj[x]) { if (c[y] >= 0) continue; c[y] = cs; s.push_back(y); }} cs++; } //update n = cs; for (ll i = 0; i < edges.size();) { edges[i].a = c[edges[i].a]; edges[i].b = c[edges[i].b]; if (edges[i].a == edges[i].b) { swap(edges[i], edges.back()); edges.pop_back(); } else { i++; } } } return res; } 
•  » » » » » » 4 years ago, # ^ |   +4 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 :DThank you for the nice implementation. It's very useful.
 » 4 years ago, # | ← Rev. 2 →   +5 https://www.codechef.com/problems/SPANTREEI would recommend trying this problem before watching the video to truly appreciate (perhaps self-discover) the algorithm :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Yeah, it's really fascinating when you discover a new algorithm even not knowing it exists already :DThank you for the new problem.
 » 4 years ago, # |   +3 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!
•  » » 4 years ago, # ^ |   +14 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 :)
 » 4 years ago, # |   +1 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.
•  » » 4 years ago, # ^ |   0 I'll add the Gaussian elimination into my list of algorithms to cover. Thanks for suggestion ;)
 » 4 years ago, # |   0 Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).