ACMICPC重要補(bǔ)充知識(shí)

.在一些有N個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪感謝閱讀個(gè)集合中。這一類問(wèn)題近幾年來(lái)反復(fù)出現(xiàn)在信息學(xué)的國(guó)際國(guó)內(nèi)賽題中，其特點(diǎn)是看似并不復(fù)謝謝閱讀雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話，往往在空間上過(guò)大，計(jì)算機(jī)無(wú)法承受；感謝閱讀即使在空間上勉強(qiáng)通過(guò)，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間精品文檔放心下載（1～3秒）內(nèi)計(jì)算出試題需要的結(jié)果，只能采用一種全新的抽象的特殊數(shù)據(jù)結(jié)構(gòu)——并查感謝閱讀集來(lái)描述。什么是并查集？并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交 集合（DisjointSets）的合精品文檔放心下載并及查詢問(wèn)題。常常在使用中以 森林來(lái)表示。集就是讓每個(gè)元素構(gòu)成一個(gè)單元素的集合， 并就是按一定順序?qū)儆谕唤M的元精品文檔放心下載素所在的集合合并。編輯本段并查集的主要操作：初始化把每個(gè)點(diǎn)所在集合初始化為其自身查找查找元素所在的集合即根節(jié)點(diǎn)合并將兩個(gè)元素所在的集合合并為一個(gè)集合.合并兩個(gè)不相交集合判斷兩個(gè)元素是否屬于同一集合輔助例題親戚(Relations)題目描述： 若某個(gè)家族人員過(guò)于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容感謝閱讀易，現(xiàn)在給出某個(gè)親戚關(guān)系圖，求任意給出的兩個(gè)人是否具有親戚關(guān)系。精品文檔放心下載規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，精品文檔放心下載那么x的親戚都是y的親戚，y的親戚也都是x的親戚。輸入格式 InputFormat 第精品文檔放心下載一行：三個(gè)整數(shù)n,m,p，（n<=5000,m<=5000,p<=5000 ），分別表示有n個(gè)人，精品文檔放心下載m個(gè)親戚關(guān)系，詢問(wèn)p對(duì)親戚關(guān)系。以下m行：每行兩個(gè)數(shù)Mi，Mj，1<=Mi，Mj<=N，精品文檔放心下載表示Ai和Bi具有親戚關(guān)系。接下來(lái) p行：每行兩個(gè)數(shù)Pi，Pj，詢問(wèn)Pi和Pj是否具感謝閱讀有親戚關(guān)系。 輸出格式 OutputFormatP 行，每行一個(gè)’Yes’或’No’。表示感謝閱讀i個(gè)詢問(wèn)的答案為“具有”或“不具有”親戚關(guān)系。var感謝閱讀father:array[1..5000]ofinteger;i,j,k,p,n,m:integer;感謝閱讀Functiongetfather(v:integer):integer;begin感謝閱讀iffather[v]=vthenexit(v);father[v]:=getfather(father[v]);getfather:=father[v];感謝閱讀end;Proceduremerge(x,y:integer);謝謝閱讀.beginx:=getfather(x);y:=getfather(y);father[x]:=y;end;Functionjudge(x,y:integer):boolean;精品文檔放心下載beginx:=getfather(x);y:=getfather(y);Ifx=ythenexit(true)elseexit(false);謝謝閱讀end;beginreadln(n,m,p);fori:=1tondofather[i]:=i;{ 預(yù)處理}精品文檔放心下載fori:=1tomdobeginread(j,k);merge(j,k);end;fori:=1topdobeginread(j,k);.ifjudge(j,k)thenwriteln('Yes')elsewriteln('No');感謝閱讀end;end.編輯本段思路點(diǎn)撥一問(wèn)題實(shí)質(zhì)初步分析覺(jué)得本題是一個(gè) 圖論中判斷兩個(gè)點(diǎn)是否在同一個(gè)連通子圖中的問(wèn)題。 對(duì)精品文檔放心下載于題目中的樣例，以人為點(diǎn)，關(guān)系為邊，建立 無(wú)向圖如下：精品文檔放心下載0-0-1{請(qǐng)補(bǔ)充圖解}比如判斷3和4是否為親戚時(shí)，我們檢查 3和4是否在同一個(gè)連通子圖中，結(jié)精品文檔放心下載果是，于是他們是親戚。又如 7和10不在同一個(gè)連通子圖中，所以他們不是親戚。感謝閱讀用圖的數(shù)據(jù)結(jié)構(gòu)的最大問(wèn)題是，我們無(wú)法存下多至 (M=)2000000條邊的圖，精品文檔放心下載后面關(guān)于算法時(shí)效等諸多問(wèn)題就免談了。用圖表示關(guān)系過(guò)于“奢侈”了。其實(shí)本題只是一個(gè)對(duì)分離集合（并查集）操作的謝謝閱讀問(wèn)題。我們可以給每個(gè)人建立一個(gè)集合，集合的元素值有他自己，表示最開(kāi)始時(shí)他不知感謝閱讀道任何人是它的親戚。以后每次給出一個(gè)親戚關(guān)系 a,b，則a和他的親戚與b和他的謝謝閱讀親戚就互為親戚了，將a所在集合與b所在集合合并。對(duì)于樣例數(shù)據(jù)的操作全過(guò)程如精品文檔放心下載下：輸入關(guān)系 分離集合初始狀態(tài)(2,4){2,4}.(5,7){2,4}{5,7}(1,3){1,3}{2,4}{5,7}(8,9){1,3}{2,4}{5,7}{8,9}感謝閱讀(1,2){1,2,3,4}{5,7}{8,9}感謝閱讀(5,6){1,2,3,4}{5,6,7}{8,9}感謝閱讀(2,3){1,2,3,4}{5,6,7}{8,9}謝謝閱讀最后我們得到4個(gè)集合{1,2,3,4},{5,6,7},{8,9}, ，于是判斷兩個(gè)人是否親戚的問(wèn)感謝閱讀題就變成判斷兩個(gè)數(shù)是否在同一個(gè)集合中的問(wèn)題。如此一來(lái)，需要的數(shù)據(jù)結(jié)構(gòu)就沒(méi)有感謝閱讀圖結(jié)構(gòu)那樣龐大了。算法需要以下幾個(gè)子過(guò)程：開(kāi)始時(shí)，為每個(gè)人建立一個(gè)集合SUB-Make-Set(x)；謝謝閱讀得到一個(gè)關(guān)系后a,b，合并相應(yīng)集合SUB-Union(a,b)；精品文檔放心下載此外我們還需要判斷兩個(gè)人是否在同一個(gè)集合中，這就涉及到如何標(biāo)識(shí)集合的問(wèn)題。我們可以在每個(gè)集合中選一個(gè)代表標(biāo)識(shí)集合，因此我們需要一個(gè)子過(guò)程給出每個(gè)集合的代表元SUB-Find-Set(a)。于是判斷兩個(gè)人是否在同一個(gè)集合中，即兩個(gè)人是否為親戚，等價(jià)于判斷SUB-Find-Set(a)=SUB-Find-Set(b)。精品文檔放心下載有了以上子過(guò)程的支持，我們就有如下算法。PROBLEM-Relations(N,M,a1, …,aM,b1,…,bM,Q,c1,…,cQ,d1,…,dQ)精品文檔放心下載1fori←1toN2doSUB-Make-Set(i)3fori←1toM4doifSUB-Find-Set(ai)?SUB-Find-Set(bi)感謝閱讀.5thenSUB-Union(ai,bi)6fori←1toQ7doifSUB-Find-Set(ci)=SUB-Find-Set(di)精品文檔放心下載8thenoutput “Yes?”9elseoutput “No?”解決問(wèn)題的關(guān)鍵便為選擇合適的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)分離集合的操作， 使算法的實(shí)現(xiàn)效謝謝閱讀率最高。二單鏈表實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)人，在同一個(gè)集合中的節(jié)點(diǎn)串成一條 鏈表就得到了單鏈表的實(shí)謝謝閱讀現(xiàn)。在集合中我們以單鏈表的第一個(gè)節(jié)點(diǎn)作為集合的代表元。于是每個(gè)節(jié)點(diǎn) x（x也謝謝閱讀是人的編號(hào)）應(yīng)包含這些信息：指向代表元即表首的指針 head[x]，指向表尾的指針感謝閱讀tail[x]，下一個(gè)節(jié)點(diǎn)的指針 next[x]。謝謝閱讀SUB-Make-Set(x)過(guò)程設(shè)計(jì)如下：SUB-Make-Set(x)10head[x]←x11tail[x]←x12next[x]←NIL求代表元的SUB-Find-Set(x)過(guò)程設(shè)計(jì)如下：謝謝閱讀SUB-Find-Set(x)13returnhead[x].前兩個(gè)過(guò)程比較簡(jiǎn)單，SUB-Union(a,b)稍微復(fù)雜一點(diǎn)。我們要做的是將 b所在感謝閱讀鏈表加到a所在鏈表尾，然后b所在鏈表中的所有節(jié)點(diǎn)的代表元指針改指 a所在鏈表謝謝閱讀的表首節(jié)點(diǎn)，如圖所示。0-0-2過(guò)程的偽代碼如下：SUB-Union(a,b)14next[tail[head[a]]]←head謝謝閱讀15tail[head[a]]←tail[head]感謝閱讀p←headwhilep?NILdohead[p]←head[a]p←next[p]現(xiàn)在我們來(lái)分析一下算法的時(shí)間效率。 SUB-Make-Set(x)和SUB-Find-Set(x)都精品文檔放心下載只需要O(1)的時(shí)間，而SUB-Union(a,b)的時(shí)間效率與b所在鏈表的長(zhǎng)度成線性關(guān)系。謝謝閱讀最壞情況下，即有操作序列 SUB-Union(N-1,N),SUB-Union(N-2,N-1), …,感謝閱讀SUB-Union(1,2)時(shí)，整個(gè)算法PROBLEM-Relations 的時(shí)間復(fù)雜度為謝謝閱讀O(N+M+N2+Q)=O(N2+M+Q)。由于算法的時(shí)間復(fù)雜度中 O(M+Q)是必需的，因此我們要讓算法更快，就要考慮感謝閱讀如何使減小O(N2)。我們想到合并鏈表時(shí)，我們可以用一種啟發(fā)式的方法：將較短的表合并到較長(zhǎng)表謝謝閱讀上。為此每個(gè)節(jié)點(diǎn)中還需包含表的長(zhǎng)度的信息。這比較容易實(shí)現(xiàn)，我們就不寫(xiě)出偽代感謝閱讀碼了。.我們來(lái)分析一下現(xiàn)在 SUB-Union(a,b)的時(shí)間復(fù)雜度。謝謝閱讀首先我們給出一個(gè)固定對(duì)象 x的代表元指針head[x]被更新次數(shù)的上界。由于每感謝閱讀次x的代表元指針被更新時(shí)，x必然在較小的集合中，因此 x的代表元指針被更新一感謝閱讀次后，集合至少含2個(gè)元素。類似地，下一次更新后，集合至少含 4個(gè)元素，繼續(xù)下精品文檔放心下載去，當(dāng)x的代表元指針被更新 ?logk?次后，集合至少含k個(gè)元素，而集合最多含n感謝閱讀個(gè)元素，所以x的代表元指針至多被更新 ?logn? 次。所以M次SUB-Union(a,b)感謝閱讀操作的時(shí)間復(fù)雜度為 O(NlogN+M)。算法總的時(shí)間復(fù)雜度為 O(NlogN+M+Q)。謝謝閱讀三分離集合的森林分離集合的另一種更快的實(shí)現(xiàn)是用有根樹(shù)來(lái)表示集合：每棵樹(shù)表示一個(gè)集合，樹(shù)精品文檔放心下載中的節(jié)點(diǎn)對(duì)應(yīng)一個(gè)人。圖示出了一個(gè)分離集合的森林。圖0-0-3每個(gè)節(jié)點(diǎn)x包含這些信息：父節(jié)點(diǎn)指針 p[x]，樹(shù)的深度rank[x]。其中rank[x]精品文檔放心下載將用于啟發(fā)式合并過(guò)程。于是建立集合過(guò)程的時(shí)間復(fù)雜度依然為 O(1)。SUB-Make-Set(x)20p[x]←x21rank[x]←0用森林的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的最大好處就是降低 SUB-Union(a,b)過(guò)程的時(shí)間復(fù)雜感謝閱讀度。SUB-Union(a,b)SUB-Link(SUB-Find-Set(a),SUB-Find-Set(b))SUB-Link(a,b)謝謝閱讀.23p[a]←b合并集合的工作只是將 a所在樹(shù)的根節(jié)點(diǎn)的父節(jié)點(diǎn)改為 b所在樹(shù)的根節(jié)點(diǎn)。這個(gè)謝謝閱讀操作只需O(1)的時(shí)間。而SUB-Union(a,b)的時(shí)間效率決定于SUB-Find-Set(x)的快精品文檔放心下載慢。SUB-Find-Set(x)24ifx=p[x]25thenreturnx26elsereturnSUB-Find-Set(p[x])感謝閱讀這個(gè)過(guò)程的時(shí)效與樹(shù)的深度成線性關(guān)系，因此其平均時(shí)間復(fù)雜度為 O(logN)，但感謝閱讀在最壞情況下（樹(shù)退化成鏈表），時(shí)間復(fù)雜度為 O(N)。于是PROBLEM-Relations感謝閱讀最壞情況的時(shí)間復(fù)雜度為 O(N(M+Q))。有必要對(duì)算法進(jìn)行優(yōu)化。感謝閱讀第一個(gè)優(yōu)化是啟發(fā)式合并。在優(yōu)化單鏈表時(shí)，我們將較短的表鏈到較長(zhǎng)的表尾，感謝閱讀在這里我們可以用同樣的方法，將深度較小的樹(shù)指到深度較大的樹(shù)的根上。這樣可以謝謝閱讀防止樹(shù)的退化，最壞情況不會(huì)出現(xiàn)。 SUB-Find-Set(x)的時(shí)間復(fù)雜度為O(logN)，謝謝閱讀PROBLEM-Relations 時(shí)間復(fù)雜度為O(N+logN(M+Q))。SUB-Link(a,b)作相應(yīng)改感謝閱讀動(dòng)。SUB-Link(a,b)27ifrank[a]>rank28thenp←a29elsep[a]←b30ifrank[a]=rank31thenrank←rank+1.然而算法的耗時(shí)主要還是花在 SUB-Find-Set(x)上。謝謝閱讀第二個(gè)優(yōu)化是路徑壓縮。它非常簡(jiǎn)單而有效。如圖所示，在SUB-Find-Set(1)時(shí)，感謝閱讀我們“順便”將節(jié)點(diǎn) 1,2,3的父節(jié)點(diǎn)權(quán)改為節(jié)點(diǎn) 4，以后再調(diào)用SUB-Find-Set(1)精品文檔放心下載時(shí)就只需O(1)的時(shí)間。0-0-4于是SUB-Find-Set(x)的代碼改為：32ifx?p[x]33thenp[x]←SUB-Find-Set(p[x])精品文檔放心下載34returnp[x]該過(guò)程首先找到樹(shù)的根，然后將路徑上的所有節(jié)點(diǎn)的父節(jié)點(diǎn)改為這個(gè)根。 實(shí)現(xiàn)時(shí)，精品文檔放心下載遞歸的程序有許多棧的操作，改成非遞歸會(huì)更快些。r←xwhiler?p[r]dor←p[r]whilex?rdoq←p[x]p[x]←rx←qreturnr.改進(jìn)后的算法時(shí)間復(fù)雜度的分析十分復(fù)雜，如果完整的寫(xiě)出來(lái)足可寫(xiě)一節(jié)，這里謝謝閱讀我們指給出結(jié)論：改進(jìn)后的 PROBLEM-Relations 其時(shí)間復(fù)雜度為謝謝閱讀O(N+(M+Q)??(M+Q,N))，其中?(M+Q,N)為Ackerman函數(shù)的增長(zhǎng)極為緩慢的逆感謝閱讀函數(shù)。你不必了解與Ackerman函數(shù)相關(guān)的內(nèi)容，只需知道在任何可想象得到的分離感謝閱讀集合數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，?(M+Q,N)?4，因此PROBLEM-Relations 的時(shí)間復(fù)雜度感謝閱讀可認(rèn)為是線性的O(N+M+Q)。解(略)編輯本段總述本題的輸入數(shù)據(jù)量很大，這使得我們的程序會(huì)在輸入中花去不少時(shí)間。如果你用感謝閱讀Pascal寫(xiě)程序，可以用庫(kù)函數(shù) SetTextBuf為輸入文件設(shè)置緩沖區(qū)，這可以使輸入過(guò)謝謝閱讀程加快不少。如果你是用 C語(yǔ)言的話，就不必為此操心了，系統(tǒng)會(huì)自動(dòng)分配緩沖區(qū)。謝謝閱讀并查集學(xué)習(xí)小節(jié)(POJ版)什么是并查集呢，我相信大家都已經(jīng)很熟悉了，在這里我就不再贅述。寫(xiě)這篇文章的主要目的不謝謝閱讀是新手教學(xué)，而是為了借POJ上相關(guān)的題目，全面的總結(jié)一下并查集問(wèn)題和它的各個(gè)變種。謝謝閱讀POJ1611TheSuspects題目大意:有n個(gè)學(xué)生（標(biāo)號(hào)為0ton-1),m個(gè)學(xué)生社團(tuán)，給出每個(gè)社團(tuán)里所有學(xué)生的標(biāo)號(hào)，并精品文檔放心下載假設(shè)0號(hào)學(xué)生患有SARS（社團(tuán)里只要用一個(gè)學(xué)生患病，則整個(gè)社團(tuán)里的學(xué)生都會(huì)被隔離），問(wèn)感謝閱讀最后一共會(huì)有多少學(xué)生被隔離？這是一個(gè)最基礎(chǔ)的并查集的應(yīng)用，掃描每一個(gè)社團(tuán)，只要兩個(gè)學(xué)生出現(xiàn)在同一個(gè)社團(tuán)，則將這兩精品文檔放心下載.個(gè)集合合并起來(lái)，最后輸出0號(hào)點(diǎn)所在集合的rank值集合（rank值記錄這個(gè)集合中的元素個(gè)數(shù)感謝閱讀并用一個(gè)flag值跟蹤0號(hào)元素所在集合標(biāo)號(hào)）即可。感謝閱讀這是并查集問(wèn)題的第一種應(yīng)用：集合合并，判斷兩點(diǎn)是不是在同一個(gè)集合，求某一個(gè)集合上的元感謝閱讀素個(gè)數(shù)等。#include<stdio.h>#defineMAX30000intf[MAX];//這里的1001只是一個(gè)示意性的數(shù)字代表初始狀態(tài)下的分支數(shù)目感謝閱讀intr[MAX];intflag;//由于不知道應(yīng)該將子樹(shù)掛到那個(gè)集合上面去，故需要一個(gè)準(zhǔn)則，這里的準(zhǔn)則是將子樹(shù)掛到謝謝閱讀//r值大的集合上面去,初始狀態(tài)下r數(shù)組的值均為一，代表每個(gè)分支下只有一個(gè)數(shù)字感謝閱讀intfind(intn){if(f[n]==n)returnn;elsef[n]=find(f[n]);returnf[n];}//查找函數(shù)，并壓縮路徑intUnion(intx,inty){.inta=find(x);intb=find(y);if(a==b)return0;elseif(r[a]<=r[b]){f[a]=b;r[b]+=r[a];if(a==flag)flag=b;}else{f[b]=a;r[a]+=r[b];if(b==flag)flag=a;}return1;}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1謝謝閱讀intmain().{intn,m;inti,j;intnum;intmaxnum=0;while(scanf("%d%d",&n,&m))感謝閱讀{flag=0;maxnum=0;inttemp1,temp2;if(n==0&&m==0)break;for(i=0;i<n;i++){f[i]=i;r[i]=1;}for(j=1;j<=m;j++){scanf("%d",&num);.for(i=0;i<num;i++){if(i==0)scanf("%d",&temp1);else{scanf("%d",&temp2);Union(temp1,temp2);}}}printf("%d\n",r[flag]);}return0;}HDOJ1213Howmanytables?#include<algorithm>#include<iostream>.#include<cstring>#defineMAX30000usingnamespacestd;intf[MAX];intr[MAX];intflag;intfind(intn){if(f[n]!=n)f[n]=find(f[n]);returnf[n];}intUnion(intx,inty){inta=find(x);intb=find(y);if(a==b)return0;elsef[a]=b;return1;}.intmain(){intn,m;inti,j;intnum,N;intmaxnum=0;scanf("%d",&N);感謝閱讀while(N!=0){ N--;scanf("%d%d",&n,&m);inttemp1,temp2;for(i=1;i<=n;i++){f[i]=i;r[i]=1;}for(j=1;j<=m;j++){cin>>temp1>>temp2;Union(temp1,temp2);}intsum=0;for(j=1;j<=n;j++).{if(f[j]==j)sum++;}cout<<sum<<endl;}system("pause");return0;}POJ2492ABug'sLife個(gè)人認(rèn)為它是初級(jí)并查集問(wèn)題的一個(gè)升級(jí)。同時(shí)這個(gè)題讓我看到了食物鏈的影子。。。精品文檔放心下載題目的大意是給出n只bug和m次觀察到的性行為，并以此為依據(jù)判斷兩只bugs是不是有同感謝閱讀性戀行為(gay)。比如3只bug12有性行為23有性行為13有性行為---->>>>>首先1,2是異性。---->>>>>然后2,3是異性?？梢酝瞥?,3是異性。但是1，3有性行為，所以可以判斷出有一定有同性戀。謝謝閱讀.剝離這個(gè)題目所賦予的外殼，我們抽出這個(gè)問(wèn)題的本質(zhì)：并查集！精品文檔放心下載其實(shí)，這里最重要的是去維護(hù)每一個(gè)點(diǎn)到集合頂點(diǎn)的偏移量。（注意：下面生造了一個(gè)詞所謂精品文檔放心下載集合元素比如說(shuō)f[i]=i,那么i就是集合元素，集合偏移量就是集合元素的偏移量）精品文檔放心下載初始狀態(tài)下，應(yīng)該是i號(hào)點(diǎn)掛在i號(hào)集合下面我們考慮一般情況：假設(shè)合并的過(guò)程已經(jīng)進(jìn)行了一部分，這樣每一個(gè)集合下面都有元素，且各感謝閱讀自對(duì)于頂點(diǎn)的偏移量都算出來(lái)了；現(xiàn)在在a集合中的元素x和b集合中的元素y進(jìn)行合并。此時(shí)有兩中情況改變偏移量；感謝閱讀1.首先是集合的合并，如果要將a,b集合合并，又要保證x,y數(shù)字的kind不相同，比如說(shuō)把b謝謝閱讀集合掛到a集合下面去。代表集合的那個(gè)元素，他的偏移量永遠(yuǎn)是0，所以b要改變偏移量，使得b里面的y在進(jìn)行變精品文檔放心下載換后要和x相異。如果kind[x]=0;kind[y]=0;那么y對(duì)應(yīng)的那個(gè)代表集合的元素的偏移量必須變成1，因?yàn)橹挥羞@精品文檔放心下載樣才能使得合并后，x,y有不同的kind;如果kind[x]=0,kind[y]=1;y對(duì)應(yīng)代表集合的元素偏移量是0，所以對(duì)應(yīng)集合偏移量還是0；精品文檔放心下載類推 kind[x]=1,kind[y]=0,同上,0；感謝閱讀kind[x]=1,kind[y]=1,y集合偏移量應(yīng)該變?yōu)?；感謝閱讀綜上可以得到一個(gè)同或的關(guān)系。用等式kind[a]=(kind[x]+kind[y]+1)%2;恰好滿足要求.謝謝閱讀2.然后是壓縮路徑時(shí)候的偏移量改變個(gè)人認(rèn)為，這個(gè)主要是解決集合合并時(shí)候產(chǎn)生的“殘余問(wèn)題”，因?yàn)樵诤喜⒓系臅r(shí)候只是考慮感謝閱讀.了集合的偏移量，至于它下面的元素一概不管。一個(gè)壓縮路徑既分離了父子元素的偏移量，又使感謝閱讀得子元素直接指向集合元素?？偠灾?，并查集的操作就是不斷地維護(hù)者各個(gè)集合中，每個(gè)元素身上對(duì)集合元素的偏移關(guān)系。感謝閱讀從而確定他們是否具有同性戀。在這個(gè)題中，假設(shè)是不存在同性戀的，所以只有找到矛盾才輸出有同性戀。謝謝閱讀#include<iostream>#include<cstdio>usingnamespacestd;#defineMAX2001intf[MAX];intkind[MAX];intn,m;inttestcase;voidinit(){inti;for(i=1;i<=n;i++){f[i]=i;kind[i]=0;}.}intFind(intn){if(f[n]==n)returnn;intt=Find(f[n]);kind[n]=(kind[n]+kind[f[n]])%2;謝謝閱讀f[n]=t;returnf[n];}intUnion(intx,inty){inta=Find(x);intb=Find(y);if(a==b){if(kind[x]==kind[y])return1;//1代表有同性戀情況}else{.f[a]=b;kind[a]=(kind[x]+kind[y]+1)%2;精品文檔放心下載}return0;}intmain(){scanf("%d",&testcase);inti,j;inta,b;intflag;for(i=1;i<=testcase;i++){flag=0;scanf("%d%d",&n,&m);init();for(j=1;j<=m;j++){scanf("%d%d",&a,&b);if(Union(a,b)){flag=1;.}}if(flag==1)printf("Scenario#%d:\nSuspiciousbugsfound!\n\n",i);精品文檔放心下載elseprintf("Scenario#%d:\nNosuspiciousbugsfound!\n\n",i);謝謝閱讀}return0;}POJ1182食物鏈中文題，讓你輸出假話的個(gè)數(shù)。其實(shí)這道題是上一道題的擴(kuò)展，如果把上一道題也想成是食物鏈精品文檔放心下載的話，就是1吃2，2吃1.而這里是三個(gè)動(dòng)物，所以同樣是維護(hù)一個(gè)偏移量，只不過(guò)多了一位罷了。感謝閱讀程序的過(guò)程實(shí)質(zhì)上就是在維護(hù)并查集，判斷是否是假話是在維護(hù)的過(guò)程中進(jìn)行的，只能算是附屬精品文檔放心下載品吧。#include<iostream>usingnamespacestd;#defineMAX50005intf[MAX];.intkind[MAX];intn,m;voidinit(){inti;for(i=1;i<=n;i++){f[i]=i;kind[i]=0;}}intFind(intn){if(f[n]==n)returnn;intt=Find(f[n]);kind[n]=(kind[n]+kind[f[n]])%3;謝謝閱讀f[n]=t;returnf[n];.}boolUnion(intx,inty,intc)感謝閱讀{if(x>n||y>n)return1;inta=Find(x);intb=Find(y);if(c==1){if(a==b){if(kind[x]!=kind[y])returntrue;}elseif(a!=b){f[b]=a;kind[b]=(kind[x]-kind[y]+3)%3;感謝閱讀}}.else{if(x==y)returntrue;if(a==b){if((kind[x]+1)%3!=kind[y])感謝閱讀returntrue;}elseif(a!=b){f[b]=a;kind[b]=(kind[x]-kind[y]+4)%3;謝謝閱讀}}returnfalse;}intmain(){inti,j;.inta,b,c;intsum=0;scanf("%d%d",&n,&m);init();for(i=1;i<=m;i++){scanf("%