集訓(xùn)隊講座第十講并查集的深化與擴展教學(xué)文稿

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

if(tree[x]==-1)

returnx;

returntree[x]=find(tree[x]);}路徑壓縮的實現(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ù)雜度分析~并查集進行n次查找的時間復(fù)雜度是:O(n*)?。。】梢钥醋鲆粋€小于5的常數(shù)K，所以進行一次并查集操作的時間復(fù)雜度為：O(K)!小試身手~Supermarket(POJ1456)SupermarketInput:4502101202301Output:80思考一下~解題小技巧！1：看數(shù)據(jù)量，估測復(fù)雜度。2：思考如何將實際題目與集合的概念聯(lián)系起來。3：如何建立模型，如何用查找

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

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

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

第一種說法是"1XY"，表示X和Y是同類。

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

此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

1）當前的話與前面的某些真的話沖突，就是假話；

2）當前的話中X或Y比N大，就是假話；

3）當前的話表示X吃X，就是假話。

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

intfather;

//父親節(jié)點

intheight;

//到父親的距離

intdep;

//有向樹的深度

intcnt;

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

intFind(intx){}

boolMerge(intx,inty){}

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

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

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

{

Make-Set(u)

ancestor[Find-Set(u)]=u

對于u的每一個孩子v

{

LCA(v)

Union(u)

ancestor[Find-Set(u)]=u

}

checked[u]=true

對于每個(u,v)屬于P

{

ifchecked[v]=true

then

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

}

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