Блог пользователя RockyB

Автор RockyB, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +218
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Great job, go on!

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Nice job, keep it up mate!

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

One more problem. 1305G

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

NotIdeal, CMaster thanks :D

»
4 года назад, # |
  Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Keep it up !

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
        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 года назад, # ^ |
          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<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;
          }
          
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +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 :D

            Thank you for the nice implementation. It's very useful.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

    Thank you for the new problem.

»
4 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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