集訓(xùn)隊(duì)講座第十講并查集的深化與擴(kuò)展概念與實(shí)現(xiàn)方式概念：并查集——不相交集合每棵樹(shù)一個(gè)集合,根為集合標(biāo)識(shí)。樹(shù)的形態(tài)并不重要,重要的是有哪些節(jié)點(diǎn)實(shí)現(xiàn)方式：一維數(shù)組的“森林表示法”。幾個(gè)定義：祖先，父親，子孫~生活中的集合~并查集的基本操作MakeSet(x)：建立一個(gè)新集合x(chóng)。x應(yīng)該不在現(xiàn)有的任何一個(gè)集合中出現(xiàn)。Find(S,x)：返回x所在集合的代表元素。Merge(x,y)：把x所在的集合和y所在的集合合并。不可忽視的弊端：無(wú)法高效的找尋兒子節(jié)點(diǎn)！??！并查集的優(yōu)化1：?jiǎn)l(fā)式并查集：讓深度較小的樹(shù)成為深度較大的樹(shù)的子樹(shù)~2：路徑壓縮：找到最久遠(yuǎn)的祖先時(shí)“順便”把它的子孫直接連接到它上面~啟發(fā)式并查集1564維護(hù)一個(gè)dep[]數(shù)組記入元素代表的有向樹(shù)的深度。每次合并操作將深度較小的集合合并到深度較大的集合中，并維護(hù)dep數(shù)組。237Dep[1]==2dep[4]==3啟發(fā)式并查集boolMerge(intx,inty){ x=find(x); y=find(y);

if(x!=y)returnfalse;

if(dep[x]<dep[y])tree[x]=y;

elseif(dep[x]>dep[y])tree[y]=x;

elsetree[x]=y,dep[y]++;

returntrue;}路徑壓縮4961111081220211661218211611209104路徑壓縮的實(shí)現(xiàn)遞歸式：intfind(intx){

if(tree[x]==-1)

returnx;

returntree[x]=find(tree[x]);}路徑壓縮的實(shí)現(xiàn)非遞歸式：int

find(intx){r=x;

while(tree[r]!=-1)r=tree[r];i=x;

while(i!=r){j=tree[i];tree[i]=r;i=j;}

returnr;

}復(fù)雜度分析~并查集進(jìn)行n次查找的時(shí)間復(fù)雜度是:O(n*)?。。】梢钥醋鲆粋€(gè)小于5的常數(shù)K，所以進(jìn)行一次并查集操作的時(shí)間復(fù)雜度為：O(K)!小試身手~Supermarket(POJ1456)SupermarketInput:4502101202301Output:80思考一下~解題小技巧！1：看數(shù)據(jù)量，估測(cè)復(fù)雜度。2：思考如何將實(shí)際題目與集合的概念聯(lián)系起來(lái)。3：如何建立模型，如何用查找

合并兩大操作來(lái)完成題目所要實(shí)現(xiàn)的動(dòng)態(tài)過(guò)程。解題的關(guān)鍵——貪心思想！思考！該如何貪心？證明貪心思想的正確性！給出一種貪心方法1：按價(jià)值從大到小排序。2：對(duì)于每個(gè)商品，選擇它目前為止能到達(dá)的最靠后的時(shí)間賣(mài)出。復(fù)雜度估計(jì)~并查集解決！并查集解決~01234567891011121314黃色：已被占用；綠色：等待被占用；粉紅：已經(jīng)無(wú)法使用，跳出。節(jié)點(diǎn)的刪除Junk-MailFilter最初每個(gè)元素都屬于自己的集合MXY：合并X所在的集合和Y所在的集合SX：把X從它所在的集合里刪除請(qǐng)問(wèn)：最后的集合個(gè)數(shù)？方法：“找替身”~2653415*4*3*2*1*6*黃色：真身綠色：替身實(shí)現(xiàn)方法~123456789…處理一個(gè)n==5的可刪除節(jié)點(diǎn)的并查集：真身替身等待做替身求元素的個(gè)數(shù)VirtualFriendsInput：13FredBarneyBarneyBettyBettyWilmaOutput：234添加變量：記變量cnt[i]表示以i為代表元素的集合的元素個(gè)數(shù)。注意：該變量只對(duì)祖先節(jié)點(diǎn)有效，非祖先節(jié)點(diǎn)的cnt沒(méi)有實(shí)際意義。如何更新cnt數(shù)組初始化每個(gè)集合的元素個(gè)數(shù)為1。當(dāng)進(jìn)行元素查找時(shí)，不做任何處理。當(dāng)進(jìn)行集合合并時(shí)，將被合并的集合的元素個(gè)數(shù)疊加到合并后的大集合中。注意：區(qū)分此處cnt[]數(shù)組和啟發(fā)式并查集中dep[]數(shù)組。合并過(guò)程~17103241196581110897164325cnt[1]==5cnt[6]==6cnt[6]==11紅色節(jié)點(diǎn)的cnt數(shù)組有效?。。≡俅紊钊耄簬?quán)值的并查集食物鏈?zhǔn)澄镦渼?dòng)物王國(guó)中有三類(lèi)動(dòng)物A,B,C，這三類(lèi)動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃C，C吃A。

現(xiàn)有N個(gè)動(dòng)物。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。

有人用兩種說(shuō)法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：

第一種說(shuō)法是"1XY"，表示X和Y是同類(lèi)。

第二種說(shuō)法是"2XY"，表示X吃Y。

此人對(duì)N個(gè)動(dòng)物，用上述兩種說(shuō)法，一句接一句地說(shuō)出K句話(huà)，這K句話(huà)有的是真的，有的是假的。當(dāng)一句話(huà)滿(mǎn)足下列三條之一時(shí)，這句話(huà)就是假話(huà)，否則就是真話(huà)。

1）當(dāng)前的話(huà)與前面的某些真的話(huà)沖突，就是假話(huà)；

2）當(dāng)前的話(huà)中X或Y比N大，就是假話(huà)；

3）當(dāng)前的話(huà)表示X吃X，就是假話(huà)。

你的任務(wù)是根據(jù)給定的N（1<=N<=50,000）和K句話(huà)（0<=K<=100,000），輸出假話(huà)的總數(shù)。試著來(lái)分析一下~1：如何來(lái)構(gòu)造集合？2：如何來(lái)判斷是否沖突？3：如何來(lái)記入信息？困惑：表示元素之間的關(guān)系并且高效的查找記入樹(shù)中每個(gè)孩子節(jié)點(diǎn)到父親節(jié)點(diǎn)的距離?。。《xheight變量height[A]%3==0：A與根節(jié)點(diǎn)是同類(lèi)。height[A]%3==1：根吃A。height[A]%3==2：A吃根。用Tree[B]=A來(lái)表示：A吃B保存有效信息Input:100711011212223233113231155Output:31XY:表示X和Y是同類(lèi)。2XY:表示X吃Y。123height[1]=0height[2]=1height[3]=1123height[1]=0height[2]=1height[3]=2判斷信息的正確性當(dāng)輸入為1XY時(shí)？當(dāng)輸入為2XY時(shí)？抓住本質(zhì)！！不同的輸入，相同的處理！回想&反思：1：為什么height[]是記錄到父親節(jié)點(diǎn)的距離？2：并查集是如何在路徑壓縮后保持它的正確性，操作上的注意點(diǎn)！溫故知新structMFset{

intfather;

//父親節(jié)點(diǎn)

intheight;

//到父親的距離

intdep;

//有向樹(shù)的深度

intcnt;

//集合的元素個(gè)數(shù)

intFind(intx){}

boolMerge(intx,inty){}

voidDelete(intx){}}tree[MAXN];綜合練習(xí)1：銀河英雄傳說(shuō)~銀河英雄傳說(shuō)~宇宙歷七九九年，銀河系的兩大軍事集團(tuán)在巴米利恩星域爆發(fā)戰(zhàn)爭(zhēng)。泰山壓頂集團(tuán)派宇宙艦隊(duì)司令萊因哈特率領(lǐng)十萬(wàn)余艘戰(zhàn)艦出征，氣吞山河集團(tuán)點(diǎn)名將楊威利組織麾下三萬(wàn)艘戰(zhàn)艦迎敵。

Mij：讓第i號(hào)戰(zhàn)艦所在的整個(gè)戰(zhàn)艦隊(duì)列，作為一個(gè)整體（頭在前尾在后）接至第j號(hào)戰(zhàn)艦所在的戰(zhàn)艦隊(duì)列的尾部。Cij：詢(xún)問(wèn)電腦，楊威利的第i號(hào)戰(zhàn)艦與第j號(hào)戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。逐步分析各個(gè)擊破集合的概念體現(xiàn)在哪里？Mij的處理方法？Cij的處理方法？需要用到哪些并查集的特征變量？合并時(shí)，這些變量該怎樣更新？定義變量：father[i]:排在戰(zhàn)艦i前面且相鄰的戰(zhàn)艦。height[i]:戰(zhàn)艦i到戰(zhàn)艦father[i]之間的戰(zhàn)艦的數(shù)量。cnt[i]:戰(zhàn)艦i所屬隊(duì)列的后方(包括i)的戰(zhàn)艦數(shù)量。(該數(shù)組只對(duì)首戰(zhàn)艦有效！)綜合練習(xí)2：Exclusive-OR另類(lèi)的并查集ConnectionsinGalaxyWar方法：把所有數(shù)據(jù)都保存下來(lái)，然后倒著處理。對(duì)于提出的問(wèn)題：及時(shí)回答，保存答案。對(duì)于刪去的樹(shù)枝：做并查集的合并處理。運(yùn)用：最近公共祖先LCA概念：LeastCommonAncestors——對(duì)于有根樹(shù)T的兩個(gè)結(jié)點(diǎn)u、v，最近公共祖先LCA(T,u,v)：詢(xún)問(wèn)一個(gè)距離根最遠(yuǎn)的結(jié)點(diǎn)x，使得x同時(shí)為結(jié)點(diǎn)u、v的祖先。祖先：從該節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)均是該節(jié)點(diǎn)的祖先。(自己是自己的祖先)

看兩種情況：26432157856431情況一：情況二：LCA(2,6)=2LCA(6,8)=3LCATarjan建樹(shù)，讀入并保存所有詢(xún)問(wèn)。對(duì)以T為根節(jié)點(diǎn)的樹(shù)進(jìn)行后根遍歷。遍歷的同時(shí)，將已訪問(wèn)的節(jié)點(diǎn)按原先的父子順序建立并查集。對(duì)于每一次詢(xún)問(wèn)Q(a,b)，若a已被訪問(wèn)，則LCA(a,b)為當(dāng)前并查集的根節(jié)點(diǎn)，保存信息。Code~LCA(u)

{

Make-Set(u)

ancestor[Find-Set(u)]=u

對(duì)于u的每一個(gè)孩子v

{

LCA(v)

Union(u)

ancestor[Find-Set(u)]=u

}

checked[u]=true

對(duì)于每個(gè)(u,v)屬于P

{

ifchecked[v]=true

then

回答u和v的最近公共祖先為ancestor[Find-Set(v)]

}

}LCATarjan算法總結(jié)解決LCA問(wèn)題的Tarjan算法利用并查集在一次DFS（深度優(yōu)先遍歷）中完成所有詢(xún)問(wèn)。它是時(shí)間復(fù)雜度為O(Na(N)+Q)，空間復(fù)雜度為O(N)的離線(xiàn)算法。LCA問(wèn)題的應(yīng)用：Howfaraway？(HDOJ2586)求在一顆無(wú)向樹(shù)中，任意兩點(diǎn)間的距離。Floyd：TimeLimitExceededLCA：Accepteddistance(a,b)=dis[a]+dis[b]-2*dis[lca(a,b)]區(qū)間最優(yōu)值RMQ把待求區(qū)間[l,r]分為兩段長(zhǎng)為len的區(qū)間左邊一段為[l,l+len-1],右邊一段為[r-len+1,r]len必須使得兩段區(qū)間覆蓋待求區(qū)間設(shè)所求數(shù)組為w那么,所求最小值就是兩個(gè)區(qū)間的