Home Explore Help
Register Sign In
schtonn
/
public
1
1
Fork 0
Files Issues 0 Pull Requests 0 Wiki
Tree: 4ce897a68f
Branches Tags
public
/
2020
/
03
/
01
/
union-find
/
index.html

index.html 15 KB
History Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264 
  1. <!DOCTYPE html>
    2. 

  2. <html>
    3. 

  3. <head>
    4. 

  4.   <meta charset="utf-8">
    5. 

  5.   
    6. 

  6. 

  7.   
    8. 

  8.   <title>并查集 | Schtonn&#39;s Blog</title>
    9. 

  9.   <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    10. 

  10.   <meta name="description" content="前置知识
 哈哈，简单到爆，没有。
 引入
 并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。">
    11. 

  11. <meta property="og:type" content="article">
    12. 

  12. <meta property="og:title" content="并查集">
    13. 

  13. <meta property="og:url" content="http://yoursite.com/2020/03/01/union-find/index.html">
    14. 

  14. <meta property="og:site_name" content="Schtonn&#39;s Blog">
    15. 

  15. <meta property="og:description" content="前置知识
 哈哈，简单到爆，没有。
 引入
 并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。">
    16. 

  16. <meta property="og:locale" content="en_US">
    17. 

  17. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105142700396.png">
    18. 

  18. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105142531778.png">
    19. 

  19. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143342729.png">
    20. 

  20. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105144059847.png">
    21. 

  21. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143532966.png">
    22. 

  22. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143644622.png">
    23. 

  23. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143847598.png">
    24. 

  24. <meta property="og:image" content="https://img-blog.csdnimg.cn/20200105144933595.png">
    25. 

  25. <meta property="article:published_time" content="2020-03-01T14:44:33.000Z">
    26. 

  26. <meta property="article:modified_time" content="2020-03-03T12:39:35.308Z">
    27. 

  27. <meta property="article:author" content="Schtonn">
    28. 

  28. <meta property="article:tag" content="struct">
    29. 

  29. <meta name="twitter:card" content="summary">
    30. 

  30. <meta name="twitter:image" content="https://img-blog.csdnimg.cn/20200105142700396.png">
    31. 

  31.   
    32. 

  32.     <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
    33. 

  33.   
    34. 

  34.   
    35. 

  35.     <link rel="icon" href="/favicon.png">
    36. 

  36.   
    37. 

  37.   
    38. 

  38.     <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
    39. 

  39.   
    40. 

  40.   
    41. 

  41. <link rel="stylesheet" href="/css/style.css">
    42. 

  42. 

  43. <meta name="generator" content="Hexo 4.2.0"></head>
    44. 

  44. 

  45. <body>
    46. 

  46.   <div id="container">
    47. 

  47.     <div id="wrap">
    48. 

  48.       <header id="header">
    49. 

  49.   <div id="banner"></div>
    50. 

  50.   <div id="header-outer" class="outer">
    51. 

  51.     <div id="header-title" class="inner">
    52. 

  52.       <h1 id="logo-wrap">
    53. 

  53.         <a href="/" id="logo">Schtonn&#39;s Blog</a>
    54. 

  54.       </h1>
    55. 

  55.       
    56. 

  56.         <h2 id="subtitle-wrap">
    57. 

  57.           <a href="/" id="subtitle">Schtonn&#39;s blog</a>
    58. 

  58.         </h2>
    59. 

  59.       
    60. 

  60.     </div>
    61. 

  61.     <div id="header-inner" class="inner">
    62. 

  62.       <nav id="main-nav">
    63. 

  63.         <a id="main-nav-toggle" class="nav-icon"></a>
    64. 

  64.         
    65. 

  65.           <a class="main-nav-link" href="/">Home</a>
    66. 

  66.         
    67. 

  67.           <a class="main-nav-link" href="/archives">Archives</a>
    68. 

  68.         
    69. 

  69.       </nav>
    70. 

  70.       <nav id="sub-nav">
    71. 

  71.         
    72. 

  72.           <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
    73. 

  73.         
    74. 

  74.         <a id="nav-search-btn" class="nav-icon" title="Search"></a>
    75. 

  75.       </nav>
    76. 

  76.       <div id="search-form-wrap">
    77. 

  77.         <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
    78. 

  78.       </div>
    79. 

  79.     </div>
    80. 

  80.   </div>
    81. 

  81. </header>
    82. 

  82.       <div class="outer">
    83. 

  83.         <section id="main"><article id="post-union-find" class="article article-type-post" itemscope itemprop="blogPost">
    84. 

  84.   <div class="article-meta">
    85. 

  85.     <a href="/2020/03/01/union-find/" class="article-date">
    86. 

  86.   <time datetime="2020-03-01T14:44:33.000Z" itemprop="datePublished">2020-Mar-01</time>
    87. 

  87. </a>
    88. 

  88.     
    89. 

  89.   </div>
    90. 

  90.   <div class="article-inner">
    91. 

  91.     
    92. 

  92.     
    93. 

  93.       <header class="article-header">
    94. 

  94.         
    95. 

  95.   
    96. 

  96.     <h1 class="article-title" itemprop="name">
    97. 

  97.       并查集
    98. 

  98.     </h1>
    99. 

  99.   
    100. 

  100. 

  101.       </header>
    102. 

  102.     
    103. 

  103.     <div class="article-entry" itemprop="articleBody">
    104. 

  104.       
    105. 

  105.         <h3 id="前置知识">前置知识</h3>
    106. 

  106. <p>哈哈，简单到爆，没有。</p>
    107. 

  107. <h3 id="引入">引入</h3>
    108. 

  108. <p>并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。 <a id="more"></a></p>
    109. 

  109. <h3 id="速度">速度</h3>
    110. 

  110. <p>他有多快呢？ <span class="math inline">\(O(*log n)\)</span> <span class="math inline">\(*log\)</span>有多可怕： |<span class="math inline">\(n\)</span>|<span class="math inline">\(*log n\)</span>| |-|-| |<span class="math inline">\((1,2]\)</span>|<span class="math inline">\(1\)</span>| |<span class="math inline">\((2,4]\)</span>|<span class="math inline">\(2\)</span>| |<span class="math inline">\((4,16]\)</span>|<span class="math inline">\(3\)</span>| |<span class="math inline">\((16,65536]\)</span>|<span class="math inline">\(4\)</span>| |<span class="math inline">\((65536,2^{65536}]\)</span>|<span class="math inline">\(5\)</span>| 所以n是<span class="math inline">\(2^{65536}\)</span>的时候复杂度还只有5。 <a href="https://sites.google.com/site/largenumbers/home/appendix/a/numbers/265536" target="_blank" rel="noopener" title="哈哈！不跨越GREATWALL打不开"><span class="math inline">\(2^{65536}\)</span></a>有多大，我把他拷进来的时候整个电脑卡死了。我不得不强制重启，然后重新写一遍这段。他有19729位。想通了吧？</p>
    111. 

  111. <h3 id="如何实现">如何实现</h3>
    112. 

  112. <p>这么高端的算法，是怎么实现的呢？ 其实</p>
    113. 

  113. <p>它的本质就是一个数组<span class="math inline">\(f[]\)</span>，和一个函数<span class="math inline">\(getf()\)</span> <span class="math inline">\(f[]\)</span>存的实际上就是几棵树。 <span class="math inline">\(f[i]\)</span>就是<span class="math inline">\(i\)</span>的父亲。 <span class="math inline">\(getf(i)\)</span>做的操作就是递归顺着<span class="math inline">\(f[i]\)</span>找<span class="math inline">\(i\)</span>所在的树的根。 <span class="math inline">\(getf()\)</span>代码： <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getf</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(f[x]==x)<span class="keyword">return</span> x;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">return</span> getf(f[x]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> <span class="math inline">\(...\)</span></p>
    114. 

  114. <p>那这个算法就很低端了<span class="math inline">\(...\)</span></p>
    115. 

  115. <p>那还讲个鬼啊<span class="math inline">\(...\)</span></p>
    116. 

  116. <p>所以</p>
    117. 

  117. <h3 id="超级优化">超级优化</h3>
    118. 

  118. <p>我们首先随机造出一些操作： <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">10</span><br><span class="line">merge 1 5</span><br><span class="line">merge 5 2</span><br><span class="line">merge 1 3</span><br><span class="line">check 2 3</span><br><span class="line">merge 3 4</span><br><span class="line">merge 6 7</span><br><span class="line">check 1 7</span><br><span class="line">merge 7 8</span><br><span class="line">merge 8 9</span><br><span class="line">merge 1 9</span><br><span class="line">check 7 4</span><br></pre></td></tr></table></figure> 其中，merge代表合并，check代表查询。 如果按照刚才所的算法，那么在第一次查询之前，就会出来这样的森林：<img src="https://img-blog.csdnimg.cn/20200105142700396.png" alt="Insert mother fucker" /> 到最后，就形成了这样一个繁杂的森林，要找到一个点的根，就需要走很长一段路。这就拉长了时间。 <img src="https://img-blog.csdnimg.cn/20200105142531778.png" alt="Insert mother fucker" /> 为了缩减时间，超级优化就出现了：路径压缩。 路径压缩其实也很简单：在<span class="math inline">\(getf()\)</span>查找根节点的同时，把自己也链接到根节点上，使得树的深度不超过2。 代码： <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getf</span><span class="params">(<span class="keyword">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(f[x]==x)<span class="keyword">return</span> x;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">return</span> f[x]=getf(f[x]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure> 发现没有，和之前的代码相比，只改了一个地方，就让时间大大压缩。 这时我们在模拟一下。 第一次合并：<img src="https://img-blog.csdnimg.cn/20200105143342729.png" alt="Insert mother fucker" /> 第二次合并时，首先寻找2,5两个节点的根节点，2的根就是2，5的根是1，于是直接把2链接到1上。 <img src="https://img-blog.csdnimg.cn/20200105144059847.png" alt="Insert mother fucker" /> 第三次，第四次合并把3链接到了1上，然后把4顺着3也链接到了1上，第五次连接了6和7。 <img src="https://img-blog.csdnimg.cn/20200105143532966.png" alt="Insert mother fucker" /> 第七次第八次链接成了<span class="math inline">\(9\rightarrow8\rightarrow7\rightarrow6\)</span>一长串，然后经过路径压缩都链接到6上了。 <img src="https://img-blog.csdnimg.cn/20200105143644622.png" alt="Insert mother fucker" /> 最后一次，把9和1链接起来了，这时深度又超过了2，一下还压缩不下去，不过没关系，查询的时候就会把它压缩的。<img src="https://img-blog.csdnimg.cn/20200105143847598.png" alt="Insert mother fucker" /> 比如查询7和4的时候就会分别寻找7和4的根节点，一路递归找上去的时候就直接把路径压缩好了，除了8还链接在6上，其他全部链接到1上了。 <img src="https://img-blog.csdnimg.cn/20200105144933595.png" alt="Insert mother fucker" /> 多么有趣啊！</p>
    119. 

  119. <h3 id="代码">代码</h3>
    120. 

  120. <p>自己想去吧，核心代码和思路都给出来了。 有一个巨大的坑，就是<span class="math inline">\(f[i]\)</span>要预设成<span class="math inline">\(i\)</span>，不然会爆炸。 加油！<del>克服恐惧的最好办法就是面对恐忄</del>快去写吧！</p>
    121. 

  121. 

  122.       
    123. 

  123.     </div>
    124. 

  124.     <footer class="article-footer">
    125. 

  125.       <a data-url="http://yoursite.com/2020/03/01/union-find/" data-id="ck7cjuv7e000dpc131fbxc304" class="article-share-link">Share</a>
    126. 

  126.       
    127. 

  127.       
    128. 

  128.   <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    129. 

  129. 

  130.     </footer>
    131. 

  131.   </div>
    132. 

  132.   
    133. 

  133.     
    134. 

  134. <nav id="article-nav">
    135. 

  135.   
    136. 

  136.     <a href="/2020/03/01/min-span-tree/" id="article-nav-newer" class="article-nav-link-wrap">
    137. 

  137.       <strong class="article-nav-caption">Newer</strong>
    138. 

  138.       <div class="article-nav-title">
    139. 

  139.         
    140. 

  140.           最小生成树
    141. 

  141.         
    142. 

  142.       </div>
    143. 

  143.     </a>
    144. 

  144.   
    145. 

  145.   
    146. 

  146.     <a href="/2020/03/01/tree-link/" id="article-nav-older" class="article-nav-link-wrap">
    147. 

  147.       <strong class="article-nav-caption">Older</strong>
    148. 

  148.       <div class="article-nav-title">树链剖分</div>
    149. 

  149.     </a>
    150. 

  150.   
    151. 

  151. </nav>
    152. 

  152. 

  153.   
    154. 

  154. </article>
    155. 

  155. 

  156. </section>
    157. 

  157.         
    158. 

  158.           <aside id="sidebar">
    159. 

  159.   
    160. 

  160.     
    161. 

  161. 

  162.   
    163. 

  163.     
    164. 

  164.   <div class="widget-wrap">
    165. 

  165.     <h3 class="widget-title">Tags</h3>
    166. 

  166.     <div class="widget">
    167. 

  167.       <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    168. 

  168.     </div>
    169. 

  169.   </div>
    170. 

  170. 

  171. 

  172.   
    173. 

  173.     
    174. 

  174.   <div class="widget-wrap">
    175. 

  175.     <h3 class="widget-title">Tag Cloud</h3>
    176. 

  176.     <div class="widget tagcloud">
    177. 

  177.       <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    178. 

  178.     </div>
    179. 

  179.   </div>
    180. 

  180. 

  181.   
    182. 

  182.     
    183. 

  183.   <div class="widget-wrap">
    184. 

  184.     <h3 class="widget-title">Archives</h3>
    185. 

  185.     <div class="widget">
    186. 

  186.       <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    187. 

  187.     </div>
    188. 

  188.   </div>
    189. 

  189. 

  190. 

  191.   
    192. 

  192.     
    193. 

  193.   <div class="widget-wrap">
    194. 

  194.     <h3 class="widget-title">Recent Posts</h3>
    195. 

  195.     <div class="widget">
    196. 

  196.       <ul>
    197. 

  197.         
    198. 

  198.           <li>
    199. 

  199.             <a href="/2020/03/02/segment-tree/">线段树</a>
    200. 

  200.           </li>
    201. 

  201.         
    202. 

  202.           <li>
    203. 

  203.             <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
    204. 

  204.           </li>
    205. 

  205.         
    206. 

  206.           <li>
    207. 

  207.             <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
    208. 

  208.           </li>
    209. 

  209.         
    210. 

  210.           <li>
    211. 

  211.             <a href="/2020/03/01/min-span-tree/">最小生成树</a>
    212. 

  212.           </li>
    213. 

  213.         
    214. 

  214.           <li>
    215. 

  215.             <a href="/2020/03/01/union-find/">并查集</a>
    216. 

  216.           </li>
    217. 

  217.         
    218. 

  218.       </ul>
    219. 

  219.     </div>
    220. 

  220.   </div>
    221. 

  221. 

  222.   
    223. 

  223. </aside>
    224. 

  224.         
    225. 

  225.       </div>
    226. 

  226.       <footer id="footer">
    227. 

  227.   
    228. 

  228.   <div class="outer">
    229. 

  229.     <div id="footer-info" class="inner">
    230. 

  230.       &copy; 2020 Schtonn<br>
    231. 

  231.       Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    232. 

  232.     </div>
    233. 

  233.   </div>
    234. 

  234. </footer>
    235. 

  235.     </div>
    236. 

  236.     <nav id="mobile-nav">
    237. 

  237.   
    238. 

  238.     <a href="/" class="mobile-nav-link">Home</a>
    239. 

  239.   
    240. 

  240.     <a href="/archives" class="mobile-nav-link">Archives</a>
    241. 

  241.   
    242. 

  242. </nav>
    243. 

  243.     
    244. 

  244. 

  245. <script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
    246. 

  246. 

  247. 

  248.   
    249. 

  249. <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
    250. 

  250. 

  251.   
    252. 

  252. <script src="/fancybox/jquery.fancybox.pack.js"></script>
    253. 

  253. 

  254. 

  255. 

  256. 

  257. <script src="/js/script.js"></script>
    258. 

  258. 

  259. 

  260. 

  261. 

  262.   </div>
    263. 

  263. </body>
    264. 

  264. </html>
    265.