Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

RockyB's blog

By RockyB, history, 5 years ago, In English

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

  1. MST
  2. Xor-MST

Problems from the readers

  1. Spanning Tree
  2. Kuroni and Antihype

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!

  • Vote: I like it
  • +218
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Great job, go on!

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Nice job, keep it up mate!

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

One more problem. 1305G

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

NotIdeal, CMaster thanks :D

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]);
    }
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes, it's called small to large technique, which you can use as well :)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Didn't know it's name, thank you!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your explanation is excellent and easy to understand. Keep it up!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm very happy that you liked the video, thanks a lot!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please post if any question related to this is on any platform.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Keep it up !

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        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)$$$

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          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<bool> boruvka(ll n, vector<edge> edges) {
              vector<bool> res(edges.size());
              while (!edges.empty()) {
                  //find local minimal edges
                  vector<ll> 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<vector<ll>> 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<ll> c(n, -1);
                  ll cs = 0;
                  for (ll i = 0; i < n; i++) {
                      if (c[i] >= 0) continue;
                      vector<ll> 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;
          }
          
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            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.

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

https://www.codechef.com/problems/SPANTREE

I would recommend trying this problem before watching the video to truly appreciate (perhaps self-discover) the algorithm :)

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Yeah, it's really fascinating when you discover a new algorithm even not knowing it exists already :D

    Thank you for the new problem.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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 :)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'll add the Gaussian elimination into my list of algorithms to cover. Thanks for suggestion ;)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RockyB (previous revision, new revision, compare).