并查集和带权并查集

秒速五厘米 2022-06-10 00:20 194阅读 0赞

一、并查集：

并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作。

主要组成部分及操作：

1，初始化：初始化后，每一个元素的父亲节点是他本身，每一个元素的祖先节点也是他本身

C++ Code

2，查找：查找一格元素所在的集合，也就是找到这个元素所在集合的祖先。(通常在查找的过程中加入路径压缩)

递归写法：

C++ Code

非递归写法：

C++ Code

ps:建议用递归写法，代码简洁。

3，合并操作：合并两个不相交集合的操作，先利用查找操作找到两个集合的祖先，将一个集合的祖先指向另一个集合的祖先

C++ Code

总的来说，并查集由一个数组，一个查找操作以及一个合并操作组成，

有的题目在合并的时候 需要根据  秩 合并，并实时更新 秩 ，只不过是多加了一个数组存储 秩。

二、带权并查集

1，概述

带权并查集就是节点存有权值的并查集，多维护一个数组来维护权值，这个权值通常表示当前点与根节点之间的关系。

2，代码实现

Java Code

<table style="width:100%;font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;">
 #include&lt;bits/stdc++.h&gt; 
 using&nbsp;namespace&nbsp;std; 
 
 const 
 &nbsp; 
 int 
 &nbsp;INF&nbsp;=&nbsp; 
 100000 
 &nbsp;+&nbsp; 
 4 
 ; 
 int 
 &nbsp;dis[INF]; 
 int 
 &nbsp;n,&nbsp;m,&nbsp;q; 
 int 
 &nbsp;fa[INF]; 
 ///初始化， 
 void 
 &nbsp;init() { &nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i&nbsp;=&nbsp; 
 1 
 ;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dis[i]&nbsp;=&nbsp; 
 0 
 ; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fa[i]&nbsp;=&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;} } 
 ///查，同时进行路径压缩以及权值数组的维护 
 int 
 &nbsp;&nbsp;Find( 
 int 
 &nbsp;&nbsp;x) { &nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (fa[x]&nbsp;==&nbsp;x) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;x; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;t&nbsp;=&nbsp;fa[x]; &nbsp;&nbsp;&nbsp;&nbsp;fa[x]&nbsp;=&nbsp;Find(fa[x]);&nbsp;&nbsp; 
 ///路径压缩 
 &nbsp;&nbsp;&nbsp;&nbsp;dis[x]&nbsp;+=&nbsp;dis[t];&nbsp;&nbsp;&nbsp;&nbsp; 
 ///更新与根的关系 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;fa[x]; } 
 ///并，注意权值数组的操作 
 void 
 &nbsp;Union( 
 int 
 &nbsp;&nbsp;x,&nbsp; 
 int 
 &nbsp;&nbsp;y,&nbsp; 
 int 
 &nbsp;&nbsp;tx,&nbsp; 
 int 
 &nbsp;ty,&nbsp; 
 int 
 &nbsp;&nbsp;d) { &nbsp;&nbsp;&nbsp;&nbsp;fa[ty]&nbsp;=&nbsp;tx; &nbsp;&nbsp;&nbsp;&nbsp;dis[ty]&nbsp;=&nbsp;dis[x]&nbsp;+&nbsp;d&nbsp;-&nbsp;dis[y]; } 
 int 
 &nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp; 
 while 
 (~scanf( 
 "%d%d%d" 
 ,&nbsp;&amp;n,&nbsp;&amp;m,&nbsp;&amp;q)) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;init(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i&nbsp;=&nbsp; 
 1 
 ,&nbsp;x,&nbsp;y,&nbsp;z;&nbsp;i&nbsp;&lt;=&nbsp;m;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///点x，y，以及他们之间的距离 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d%d" 
 ,&nbsp;&amp;x,&nbsp;&amp;y,&nbsp;&amp;z); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;&nbsp;tx&nbsp;=&nbsp;Find(x); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;&nbsp;ty&nbsp;=&nbsp;Find(y); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (tx&nbsp;!=&nbsp;ty) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Union(x,&nbsp;y,&nbsp;tx,&nbsp;ty,&nbsp;z); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i&nbsp;=&nbsp; 
 0 
 ,&nbsp;x,&nbsp;y;&nbsp;i&nbsp;&lt;&nbsp;q;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d" 
 ,&nbsp;&amp;x,&nbsp;&amp;y); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (Find(x)&nbsp;==&nbsp;Find(y)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n" 
 ,&nbsp;dis[y]&nbsp;-&nbsp;dis[x]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "-1\n" 
 ); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp; 
 0 
 ; } 
 </div></td> 
 </tr> 
 </tbody> 
</table>