Hackerank: Road in hacker land

Feb. 20, 2018

Introduction

It is my favorite algorithm called union find algorithm. It can be Kruskal algorithm. I did have a lot of practice recently. It is so good to come back to work on the algorithm again.

Algorithm study 

Plan to review the algorithm by studying the blog.

题意

给一个联通的无向图，求所有点对之间的距离和。其中每条边的距离都是 2 的幂且互不相同。

题解

• 每条边距离为 2 的幂且不相同，意味着选择长的边很可能是不好的。
• 这道题跑最短路显然不大可能，因为需要求所有点对的距离和。最优解是最小生成树，接下来来证明。
• 假设最优解不是最小生成树，那么去掉其中长度最长的边（长度为 k）后再增加若干条长度小于 k 的边仍能使其联通。先去掉最长的边，那么有一些点对会无法联通，这些点对的距离至少为 2^k，现在增加一些边使其联通，那么这些点对的距离至多是 2^0+2^1+2^2+⋯+2^k−1<2^k，从而得到一个更优解，所以假设不成立。
• 既然是最小生成树，那么需要求一下这棵树上每条边的贡献，这个问题就比较简单了，跑一边 dfs 即可。
• 
  

Coding

Please use the code for Union find algorithm Island count II for the template, and apply the same technique on this algorithm. Here is the link. 

Quick union algorithm

I like to review the practice on quick union algorithm. Here is the link: 

Quick find algorithm

I reviewed the quick find algorithm more than one month ago. Here is the link: 

A mock interview discussion

I remembered that the peer gave me the question and test my disjoint set data structure. I chose to use depth first search and then had some idea to use hashset only data structure. Here is the discussion.