schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264
							<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  <title>并查集 | Schtonn&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="前置知识
 哈哈，简单到爆，没有。
 引入
 并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。">
<meta property="og:type" content="article">
<meta property="og:title" content="并查集">
<meta property="og:url" content="http://yoursite.com/2020/03/01/union-find/index.html">
<meta property="og:site_name" content="Schtonn&#39;s Blog">
<meta property="og:description" content="前置知识
 哈哈，简单到爆，没有。
 引入
 并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105142700396.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105142531778.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143342729.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105144059847.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143532966.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143644622.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105143847598.png">
<meta property="og:image" content="https://img-blog.csdnimg.cn/20200105144933595.png">
<meta property="article:published_time" content="2020-03-01T14:44:33.000Z">
<meta property="article:modified_time" content="2020-03-03T12:39:35.308Z">
<meta property="article:author" content="Schtonn">
<meta property="article:tag" content="struct">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img-blog.csdnimg.cn/20200105142700396.png">
  
    <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

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

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Schtonn&#39;s Blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">Schtonn&#39;s blog</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <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>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-union-find" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/union-find/" class="article-date">
  <time datetime="2020-03-01T14:44:33.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      并查集
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>哈哈，简单到爆，没有。</p>
<h3 id="引入">引入</h3>
<p>并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。 <a id="more"></a></p>
<h3 id="速度">速度</h3>
<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>
<h3 id="如何实现">如何实现</h3>
<p>这么高端的算法，是怎么实现的呢？ 其实</p>
<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>
<p>那这个算法就很低端了<span class="math inline">\(...\)</span></p>
<p>那还讲个鬼啊<span class="math inline">\(...\)</span></p>
<p>所以</p>
<h3 id="超级优化">超级优化</h3>
<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>
<h3 id="代码">代码</h3>
<p>自己想去吧，核心代码和思路都给出来了。 有一个巨大的坑，就是<span class="math inline">\(f[i]\)</span>要预设成<span class="math inline">\(i\)</span>，不然会爆炸。 加油！<del>克服恐惧的最好办法就是面对恐忄</del>快去写吧！</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/union-find/" data-id="ck7cjuv7e000dpc131fbxc304" class="article-share-link">Share</a>
      
      
  <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>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2020/03/01/min-span-tree/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          最小生成树
        
      </div>
    </a>
  
  
    <a href="/2020/03/01/tree-link/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">树链剖分</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <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>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <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>
    </div>
  </div>

  
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/03/02/segment-tree/">线段树</a>
          </li>
        
          <li>
            <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
          </li>
        
          <li>
            <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
          </li>
        
          <li>
            <a href="/2020/03/01/min-span-tree/">最小生成树</a>
          </li>
        
          <li>
            <a href="/2020/03/01/union-find/">并查集</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 Schtonn<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

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


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

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


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


  </div>
</body>
</html>