知識總覽：

并查集：

并查集就是一種集合，合并+查找====》集合

集合中元素只有2種關系，屬于這個集合或者屬于另外一個集合(或者說不屬于這個集合)

一個集合里有好多元素，把同類型的元素構造成一棵樹，其他類元素構造成另外一棵樹，這個元素屬于哪個集合就用這棵樹的根節(jié)點表示，討論哪個元素屬于哪個集合，就是找這個元素所在樹的根節(jié)點。森林是由多個互不相交的樹構成的

用互不相交的樹來表示集合的用途：

1.判斷某個元素屬于哪個集合------》從該元素出發(fā)，一路向北查到該元素所在根節(jié)點，根節(jié)點是哪個就是哪個樹，哪個集合

2.判斷2個元素是否從屬相同集合---》各個元素一路向北查到各元素所在根節(jié)點，就是各元素所在哪個樹，哪個集合，再判斷2個根節(jié)點是否相等，相等即為在同一個集合，不相等即為在不同集合

3.合并子集操作。即把2個集合合并成一個集合，可以把一個子集放到另外一個子集里成為另外一個子集的子集。即把一棵樹放到另外一棵樹里成為另外一棵樹的孩子。如例子喜歡紫葡萄、綠葡萄的人各自為一個子集，則可把2個子集合并成一個都喜歡葡萄的集合，即可讓喜歡紫葡萄的樹歸屬到喜歡綠葡萄樹的子樹即可

?

為什么用樹的雙親表示法表示并查集：用孩子節(jié)點字段中的parent指針指向該節(jié)點的父節(jié)點所在的數組下標，查詢父節(jié)點快，查找孩子節(jié)點慢(因為要遍歷所有的節(jié)點，找parent是該節(jié)點的)，而并查集的查是一路向北找父節(jié)點的，所以用雙親表示法更容易找父節(jié)點，并且并查集的并是把一棵樹A合并到另外一棵樹B下成為樹B的子樹，如果用雙親表示法直接把A的根節(jié)點的parent字段改成B的根節(jié)點就可完成合并，綜上，用雙親表示法表示并查集很方便。

并查集的存儲結構：

就是長度為n的int型數組S。和樹的雙親表示法類似，即假如所有元素個數為n，則定義一個長度為n的int型數組S，把元素依次放在數組中，每個元素對應一個下標，數組中的值即為父節(jié)點的數組下標，即實際數組存儲的是該元素父節(jié)點的索引下標，注意的是該數組S存儲的是所有元素的父節(jié)點的數組下標，即使有的節(jié)點元素不屬于同一集合，沒有父節(jié)點的數組值為-1，如最后一張圖，三個樹三個集合統(tǒng)一放到S數組里，根節(jié)點ACD在數組中的值為-1，如果要把C合并到A，則直接修改C對應的數組值為為A節(jié)點的下標即可，即從-1修改為0，就完成了并查集的合并，并查集的查找即查找父節(jié)點直接查找S中的值可根據下標直接定位到父節(jié)點元素

?

代碼實現：

并查集的初始化操作：初始化S[]數組中的值都為-1。并查集就是用一個Int型的數組進行表示即UFSets，開始并不知道這些元素是否屬于一個集合，所以把每個元素都初始化為一個個單獨的子集，即一個元素一個集合，完成這個操作只需要把數組上的每個元素的值設為-1即可，即表示每個元素都是單獨的子集。然后開始進行并查操作，應該屬于同一個集合的元素就合并成一個集合。

并查集的查Find操作：

即找某個元素的所在樹的根節(jié)點。Find中x指的是元素所在數組中的下標(注意不是S[]數組中的值，S[]數組中的值是元素下標的父節(jié)點下標值)，目前看數組S好像就是存的是元素的父節(jié)點數組下標，數組中沒其他字段內容。如要查L元素即下標為11即x=11的屬于哪個集合，一路向北查到根節(jié)點，S[11]=4>=0,即下一輪while循環(huán)，X=4，S[4]=1>= 0，下一輪while循環(huán)，X=1,S[1]=0>=0,下一輪while循環(huán)，X=0，S[0]=-1<=0，退出while循環(huán)，返回X=0，依次為查找L的父節(jié)點為E，E的父節(jié)點B，B的父節(jié)點A，A沒有父節(jié)點，結束。即L屬于A節(jié)點所在集合。

并查集的并Union操作：

即將2個不想交的集合合并成一個，修改其中一個集合中的父節(jié)點為另外一個節(jié)點的下標。要傳入2個集合(2個樹)的根節(jié)點下標，如合并AC集合，要傳入A數組下標0，C數組下標2，即Root1=0，Root2=2，即把Root2合并到Root1即合并C到A，先判斷Root1==Root2直接返回即2個相同集合的不用合并，再把S[Root2]=Root1，即S[2]=0，即把要變成子樹的根節(jié)點S[]中的值變成另外一個樹的根節(jié)點數組下標，即修改Root2的父節(jié)點數組索引下標由-1改為0

如果在合并的時候給的Root1和Root2節(jié)點并不是集合的根節(jié)點，那么先通過Find操作找到這倆節(jié)點的根節(jié)點，再進行Union操作

時間復雜度分析：

union操作只需修改數組中的值，時間復雜度為O(1)

Find操作要根據樹的形態(tài)確定時間復雜度，如果是最壞單支情況可能需要進行n次while循環(huán)即O(n)，好的情況可能只需找一層或不用找吧即O(1)，即讓樹的高度h變低有助于減少時間復雜度

union操作的優(yōu)化

讓樹的時間復雜度變小，即讓樹的高度h變小，則在合并時讓小樹合大樹。因為小樹合大樹只是讓小樹的父節(jié)點變成大樹的，大樹的高度h不會改變(大樹一般會比小樹高，合到大樹之后，小樹只是作為一個子樹出現，一般應該不會影響大樹的高度)，如果讓大樹合到小樹上，大樹的高度h一般>小樹高度h，合過去之后大樹作為子樹出現，則起碼大樹高度h還高一層，且大樹節(jié)點數>小樹節(jié)點數，則大樹節(jié)點在進行Find操作時都要再至少加一層高度

具體優(yōu)化：

如果是各個集合的根節(jié)點，優(yōu)化前根節(jié)點在S[]中的值為-1，優(yōu)化后讓S[]中的值<0，但是S[]代表的值為整個樹的節(jié)點個數，比如A集合即A樹有6個節(jié)點，A的index=0，優(yōu)化前S[0]=-1，優(yōu)化后S[0]=-6，同理C集合，S[2]=-1變成S[2]=-2，小樹合大樹即C合到A(因為C有2個節(jié)點，A有6個節(jié)點，A是大樹)，合并之后，A中多了2個節(jié)點，即A共有8個節(jié)點，S[0]=-8,C不再是根節(jié)點，變成S[2]=S[0]

優(yōu)化代碼實現如下：

1.用根節(jié)點的絕對值表示樹的節(jié)點總數2.union操作，小樹合并大樹

過程：目前認為傳入的2個節(jié)點都是根節(jié)點，如果不是先去做find操作。判斷Root1和Root2是否相等即是否是相同集合，相同集合不做操作直接return。如果S[Root2]>S[Root1]則Root2合并到Root1(2個S值都為負數的情況下，證明root1的節(jié)點數更多)，Root1是大樹Root2是小樹，讓S[Root1]+=S[Root2]，S[Root2]=Root1，即Root1總節(jié)點數增加，Root2父節(jié)點改變成Root1，相反同上個過程

優(yōu)化之后結果：Find操作時間復雜度變成O(log2n),union操作時間復雜度不變還是O(1)，合并后構造的樹的高度不超過log2n向下取整+1

知識回顧：

寫得好羅里吧嗦，其實知識點并不復雜。。。。。。。。。。。。?

?