版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
例如:如果已經(jīng)得到完整的家譜,判斷兩個(gè)人是否親戚應(yīng)該是可行的,但如果兩個(gè)人的最近公共祖先與他們相隔好幾代,使得家譜十分龐大,那么檢驗(yàn)親戚關(guān)系就十分復(fù)雜。在這種情況下,就需要應(yīng)用并查集。為了將問題簡化,將得到一些親戚關(guān)系的信息,如Marry和Tom是親戚,Tom和Ben是親戚,等等。從這些信息中,可以推出Marry和Ben是親戚。7.9.1什么叫并查集7.9并查集1/15輸入:第一局部以N,M開始。N為問題涉及的人的個(gè)數(shù)〔1≤N≤20000〕。這些人的編號為1,2,3,…,N。下面有M行〔1≤M≤1000000〕,每行有兩個(gè)數(shù)ai、bi,表示ai和bi是親戚。第二局部以Q開始。以下Q行有Q個(gè)詢問〔1≤Q≤1000000〕,每行為ci和di,表示詢問ci和di是否為親戚。輸出:對于每個(gè)詢問ci、di,輸出一行:假設(shè)ci和di為親戚,那么輸出“Yes〞,否那么輸出“No〞。解決分類問題2/15輸入樣例:107 //N=10,M=7245713891256233 //Q=33471089類似于離散數(shù)學(xué)中的等價(jià)類問題:給定一個(gè)集合U和一個(gè)等價(jià)關(guān)系R,產(chǎn)生具有等價(jià)關(guān)系的等價(jià)類。3/15采用集合的思路求解輸入關(guān)系別離集合初始狀態(tài){1},{2},{3},{4},{5},{6},{7},{8},{9},{10}〔2,4〕{1},{2,4},{3},{5},{6},{7},{8},{9},{10}〔5,7〕{1},{2,4},{3},{5,7},{6},{8},{9},{10}〔1,3〕{1,3},{2,4},{5,7},{6},{8},{9},{10}〔8,9〕{1,3},{2,4},{5,7},{6},{8,9},{10}〔1,2〕{1,2,3,4},{5,7},{6},{8,9},{10}〔5,6〕{1,2,3,4},{5,6,7},{8,9},{10}〔2,3〕{1,2,3,4},{5,6,7},{8,9},{10}4/15{1,2,3,4},{5,6,7},{8,9},{10}34
3、4在同一個(gè)集合中Yes求解:710
7、10不在同一個(gè)集合中No89
8、9在同一個(gè)集合中Yes結(jié)果集合:5/15并查集的數(shù)據(jù)結(jié)構(gòu)記錄了一組別離的動態(tài)集合S={S1,S2,…,Sk}。每個(gè)動態(tài)集合Si〔1≤i≤k〕通過一個(gè)“代表〞加以標(biāo)識,該代表即為所代表的集合中的某個(gè)元素。對于集合Si,選取其中哪個(gè)元素作為代表是任意的。6/157對于給定的編號為1~n的n個(gè)元素,x表示其中的一個(gè)元素,設(shè)并查集為S,并查集的實(shí)現(xiàn)需要支持如下運(yùn)算:MAKE_SET(S,n):初始化并查集S,即S={S1,S2,…,Sn},每個(gè)動態(tài)集合Si〔1≤i≤n〕僅僅包含一個(gè)編號為i的元素,該元素作為集合Si的“代表〞。FIND_SET(S,x):返回并查集S中x元素所在集合的代表。UNION(S,x,y):在并查集S中將x和y兩個(gè)元素所在的動態(tài)集合〔例如Sx和Sy〕合并為一個(gè)新的集合Sx∪Sy。
用有根樹來表示集合,樹中的每個(gè)結(jié)點(diǎn)包含集合的一個(gè)成員,每棵樹表示一個(gè)集合。多個(gè)集合形成一個(gè)森林,以每棵樹的樹根作為集合的代表,并且根結(jié)點(diǎn)的父結(jié)點(diǎn)指向其自身,樹上的其他結(jié)點(diǎn)都用一個(gè)父指針表示它的附屬關(guān)系。
7.9.2并查集的算法實(shí)現(xiàn)8/15在并查集中,每個(gè)別離集合對應(yīng)的一棵樹,稱為別離集合樹。整個(gè)并查集也就是一棵別離集合森林。4個(gè)集合{1,2,3,4}、{5,6,7}、{8,9}、{10},分別以4、7、9和10表示對應(yīng)集合的編號。4321{1,2,3,4}集合756{5,6,7}集合98{8,9}集合10{10}集合9/15在一棵高度較低的樹中查找根結(jié)點(diǎn)的編號〔即該集合的代表〕所花的時(shí)間較少,如何保證構(gòu)造的別離集合樹較低呢?兩棵別離集合樹A和B,高度分別為hA和hB,那么假設(shè)hA>hB,應(yīng)將B樹作為A樹的子樹;否那么,將A樹作為B樹的子樹??傊?,總是高度較小的別離集合樹作為子樹。得到的新的別離集合樹C的高度hC,以B樹作A樹的子樹為例:hC=MAX{hA,hB+1}。10/15typedefstructnode{intdata; //結(jié)點(diǎn)對應(yīng)人的編號intrank; //結(jié)點(diǎn)秩,大致為樹的高度intparent; //結(jié)點(diǎn)對應(yīng)雙親下標(biāo)}UFSTree; //并查集樹的結(jié)點(diǎn)類型并查集采用順序方法存儲,結(jié)點(diǎn)的類型聲明如下:11/15〔1〕并查集樹的初始化voidMAKE_SET(UFSTreet[],intn)//初始化并查集樹{inti;for(i=1;i<=n;i++){ t[i].data=i; //數(shù)據(jù)為該人的編號 t[i].rank=0; //秩初始化為0 t[i].parent=i; //雙親初始化指向自已}}12/15〔2〕查找一個(gè)元素所屬的集合intFIND_SET(UFSTreet[],intx)//在x所在子樹中查找集合編號{if(x!=t[x].parent) //雙親不是自已 return(FIND_SET(t,t[x].parent));//遞歸在雙親中找x
else return(x); //雙親是自已,返回x}13/1514/15〔3〕兩個(gè)元素各自所屬的集合的合并voidUNION(UFSTreet[],intx,inty)//將x和y所在的子樹合并{x=FIND_SET(t,x); //查找x所在別離集合樹的編號y=FIND_SET(t,y); //查找y所在別離集合樹的編號if(t[x].rank>t[y].rank) //y結(jié)點(diǎn)的秩小于x結(jié)點(diǎn)的秩 t[y].parent=x; //將y連到x結(jié)點(diǎn)上,x作為y的雙親結(jié)點(diǎn)else //y結(jié)點(diǎn)的秩大于等于x結(jié)點(diǎn)的秩{ t[x].parent=y; //將x連到y(tǒng)結(jié)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 寧波浙江寧波市鄞州區(qū)第二醫(yī)院醫(yī)共體姜山分院編外人員招聘筆試歷年典型考點(diǎn)(頻考版試卷)附帶答案詳解
- 2024年03月浙江泰隆商業(yè)銀行股份有限公司嘉興海鹽支行2024年招考5名客戶經(jīng)理筆試歷年參考題庫附帶答案詳解
- 2024年中國聚丙烯塑料紡織袋市場調(diào)查研究報(bào)告
- 2024年中國組裝筆市場調(diào)查研究報(bào)告
- 2024年鋁合金門窗產(chǎn)品出口貿(mào)易合同范本3篇
- 2025年度鈑金展柜租賃與維護(hù)保養(yǎng)合同范本3篇
- 2025年環(huán)保電子產(chǎn)品ROHS檢測與質(zhì)量保障服務(wù)協(xié)議
- 2025年度體育設(shè)施場地租賃協(xié)議3篇
- 2025版房地產(chǎn)項(xiàng)目產(chǎn)權(quán)交易合作協(xié)議書范本3篇
- 2025年工地食堂租賃合同包含員工餐飲補(bǔ)貼方案3篇
- 法治副校長進(jìn)校園教育
- 北京市石景山區(qū)2023-2024學(xué)年七年級上學(xué)期期末考試數(shù)學(xué)試卷(含答案)
- 2025版寒假特色作業(yè)
- Unit 7 Will people have robots Section B 1a-1e 教學(xué)實(shí)錄 2024-2025學(xué)年人教版英語八年級上冊
- 江西省吉安市2023-2024學(xué)年高一上學(xué)期1月期末考試政治試題(解析版)
- 國內(nèi)外航空安全形勢
- 《雷達(dá)原理》課件-1.1.6教學(xué)課件:雷達(dá)對抗與反對抗
- 2024年版汽車4S店商用物業(yè)租賃協(xié)議版B版
- 微信小程序云開發(fā)(赤峰應(yīng)用技術(shù)職業(yè)學(xué)院)知到智慧樹答案
- 遼寧省撫順市清原縣2024屆九年級上學(xué)期期末質(zhì)量檢測數(shù)學(xué)試卷(含解析)
- 2024-2025學(xué)年上學(xué)期福建高二物理期末卷2
評論
0/150
提交評論