并查集及其應(yīng)用課件

并查集及其應(yīng)用幽默來自智慧，惡語來自無能并查集及其應(yīng)用、引例例一、親戚(relation)問題描述:或許你并不知道,你的某個朋友是你的親戚。他可能是你的曾祖父J外公的女婿的外甥女的表姐的孫子!!!得到元整的家譜,判斷兩個人是否親戚應(yīng)該是可行的,但如果兩個人的最近公共祖先與他們相隔好幾代,使得家譜十分龐大,那么檢驗親戚關(guān)系實非人力所能及。在這種情況下,最好的幫手就是計算機。為了將問題簡化,你將得到一些親戚關(guān)系的信息,如Marry和Tom是親戚,Tom和Ben是親戚,等等。從這些信息中,你可以推出Marry和Ben是親戚請寫一個程序,對于我們的關(guān)于親戚關(guān)系的提問,以最快的速度給出答案。并查集及其應(yīng)用輸入由兩部分組成第一部分以N,M開始。N為問題涉及的人的個數(shù)(1≤N≤20000。這些的編號為1,2,3,,N。下面有M行(1≤M≤1000000),每行有兩個a,b;,表示已知a和b,是親戚第二部分以Q開始。以下Q行有Q個詢問(1≤Q≤1000,每行為c1d1,表示詢問c1和d是否為親戚輸出:對于每個詢問c1,d1,輸出一行:若c1和d1為親戚,則輸出“Ye否則輸出“No”。并查集及其應(yīng)用輸入樣例(relation.in):1072457輸出樣例(relation.out)Yes5623Ye3471089并查集及其應(yīng)用問題分析:將每個人抽象成為一個點,數(shù)據(jù)給出M個邊的關(guān)系,兩個人是親戚的時候兩點間有一條邊。很自然的就得到了一個N個頂點邊的圖論模型,注意到傳遞關(guān)系,在圖中一個連通塊中的任點之間都是親戚。對于最后的Q個提問,即判斷所提問的兩個個連通塊中。用傳統(tǒng)的思路,馬上可以反應(yīng)過來,對于輸入的N個點M條邊,找出連通塊,然后進行判斷。但這種實現(xiàn)思路首先必須保存M條邊,然后再進行普通的遍歷算法,不管是從空間還是時間上看,效率都不高。再進一步考慮,如果把題目的要求改一改,對于邊和提問相間輸入,即把題目改成:并查集及其應(yīng)用第一行是N,M。N為問題涉及的人的個數(shù)(1≤N≤20000)。這些人的編號為1,2,3,…,N下面有M行(1≤M≤200000每行有三個數(shù)k,a,b表示兩個元素,k為0或1,k為1時表示這是一條邊的信息,即表示和是親戚關(guān)系;k為0時表示這是一個提問,要你根據(jù)此行以前所得到的信息,判斷a和b,是否是親戚,對于每條提問回答Yes或者No這個問題比原問題更復雜些,需要在任何時候回答提問的兩個人的關(guān)系,并且對于信息提示還要能立即合并兩個連通塊。采用連通圖思想顯然在實現(xiàn)上就有所困難,因為要實時地表示人與人之間的關(guān)系。并查集及其應(yīng)用用集合的思路,對于每個人建立一個集合,開始的時候集合元素是這個人本身,表示開始時不知道任何人是他的親戚。以次給出一個親戚關(guān)系時,就將兩個集合合并。這樣實時地得了在當前狀態(tài)下的集合關(guān)系。如果有提問,即在當前得到的結(jié)果中看兩元素是否屬于同一集合。對于樣例數(shù)據(jù)的解釋如下圖:并查集及其應(yīng)用輸入關(guān)系分離集合初始狀態(tài){1}{2}131415}16{7}{8}9}(10}(2,4)1}{2,4}{3}{5}{6}{7}{8}{9}{10}{1}2,4}{3}{5,7}{6}{8}{9}{101,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}{1,2,3,4}{5,6,7}{8,9}{10并查集及其應(yīng)用用集合的思路,對于每個人建立一個集合,開始的時候集合元素是這個人本身,表示開始時不知道任何人是他的親戚。以每次給出一個親戚關(guān)系時,就將兩個集合合并。這樣實時地得在當前狀態(tài)下的集合關(guān)系。如果有提問,即在當前得到的結(jié)素是否屬于同一集合。對于樣例數(shù)據(jù)的解釋如下圖:由上圖可以看出,操作是在集合的基礎(chǔ)上進行的,沒有必要保存所有的邊,而且每一步得到的劃分方式是動態(tài)的。如何來實現(xiàn)以上的算法思想呢?我們就用到并查集并查集及其應(yīng)用二、并查集的基本思想1、什么叫并查集并查集(unlon-findset)是一種用于分離集合操作的抽據(jù)類型。它所處理的是“集合”之間的關(guān)系,即動態(tài)地維處理集合元素之間復雜的關(guān)系,當給出兩個元素的一個無序?qū)?a,b)時,需要快速“合并”a和b分別所在的集合,這其間需要反復“查找”某元素所在的集合?！安ⅰ薄ⅰ安椤焙图比钟纱硕鴣?。在這種數(shù)據(jù)類型中,n個不同的元素被分為若干組。每組是一個集合,這種集合叫做分離集合(disjointset)。并查集支持查找一個元素所屬的集合以及兩個元素各自所屬的集合的合并。并查集及其應(yīng)用二、并查集的基本思想例如,有這樣的問題:初始時n個元素分屬不同的n個集合,通過不斷的給出元素間的聯(lián)系,要求實時的統(tǒng)計元素間的關(guān)系否存在直接或間接的聯(lián)系)。這時就有了并查集的用武之地了。元素間是否有聯(lián)系,只要判斷兩個元素是否屬于同一個給出元素間的聯(lián)系,建立這種聯(lián)系,則只需合并兩個元素各自所屬的集合。這些操作都是并查集所提供的并查集本身不具有結(jié)構(gòu),必須借助一定的數(shù)據(jù)結(jié)構(gòu)以得到支持和實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的選擇是一個重要的環(huán)節(jié),選擇不同的數(shù)據(jù)結(jié)構(gòu)可能會在查找和合并的操作效率上有很大的差別,但操作實現(xiàn)都比較簡單高效。并査集的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)方法很多,一般用的比較多的是,數(shù)組實現(xiàn)、鏈表實現(xiàn)和樹實現(xiàn)36、自己的鞋子，自己知道緊在哪里?！靼嘌?/p>

37、我們唯一不會改正的缺點是軟弱。