【poj】
第一題 poj 1182 食物鍊
<a target="_blank" href="http://poj.org/problem?id=1182">點選打開連結poj 1182</a>
思路: 帶權并查集
分析:
1 典型的帶權并查集的題目
2 如果x和y是同類的關系認為是0，如果是x吃y那麼關系認為是1,那麼x和y的關系為2就說明y吃x
3 那麼如果x和y同類則rank[x] == rank[y] , 如果x吃y那麼rank[x] == (rank[y]+1)%3 , 注意mod3的使用
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8019237">點選檢視代碼</a>
第二題 poj 1308 Is It A Tree?
<a target="_blank" href="http://poj.org/problem?id=1308">點選打開連結 poj 1308</a>
思路: 普通并查集
1 題目輸入一些邊，要我們去判斷是否是一棵樹
2 根據題目的意思，空樹也是樹或者隻有一個跟節點的是樹
3 不滿足的情況是邊是自環即x == y的情況，還有就是加入一條邊形成環。由于樹是一個連通分量，是以最後判斷一下是不是隻有一個連通分量
4 輸入的邊可能是自環，這個是一個trick
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8027356">點選檢視代碼</a>
第三題 poj 1611 The Suspects
<a target="_blank" href="http://poj.org/problem?id=1611">點選打開連結poj 1611</a>
1 題目最終要求的是和0同一個集合的元素的個數
2 比較簡單的題，線上更新并查集，開個數組記錄目前集合的元素的個數
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8012224">點選檢視代碼</a>
第四題 poj 1703 Find them, Catch them
<a target="_blank" href="http://poj.org/problem?id=1703">點選打開連結poj 1703</a>
思路: 簡單帶權并查集
1 題目要詢問給定的x和y是否是同一個動物
2 我們假設如果不同，那麼權值為1，否則為0。是以對于給定的x和y，那麼如果x和y不在一個集合裡面那麼就是不确定，否則就可以根據rank來判斷是什麼關系
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8016538">點選檢視代碼</a>
第五題 poj 1988 Cube Stacking
<a target="_blank" href="http://poj.org/problem?id=1988">點選打開連結 poj 1988</a>
1 題目給定2種指令 M x y把x的集合放在y集合的上面，C x求x的下面有多少個元素
2 我們用rank[x]表示x以下有多少個元素，那麼對于指令M x y我們始終把左邊的合并到右邊，那麼這樣rank就滿足壓縮的性質
3 但是因為這邊的合并和普通不一樣，它是把x所在的集合放在y所在集合上面，實際上是x的跟節點合并到y集合的最遠點，是以我們應該開個數組記錄目前集合最遠的點
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8026631">點選檢視代碼</a>
第六題 poj 2236 Wireless Network
<a target="_blank" href="http://poj.org/problem?id=2236">點選打開連結poj 2236</a>
1 初始值所有的電腦都是壞的，然後給肯定n個點的坐标，隻有距離不大于d的才認為連通的
2 現在給定兩種操作，O p表示編号為p的電腦被修好了，S p q詢問p q是否是連通的
3 簡單的并查集，先預處理出所有的點到其他點的距離，然後每一次修好一個電腦之後就去更新并查集，遇到詢問的時候隻要判斷是否在同一個集合裡面即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8012255">點選檢視代碼</a>
第七題 poj 2492 A Bug's Life
<a target="_blank" href="http://poj.org/problem?id=2492">點選打開連結poj 2492</a>
1 用rank[i] = 0表示關系相同，用rank[i] = 1表示關系不同
2 在輸入的時候把兩個元素之間的關系建立起來，然後判斷目前的兩個元素是否在同一個集合裡面，如果是則判斷是不是屬于同一個類型即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8018962">點選檢視代碼</a>
第八題 poj 2524 Ubiquitous Religions
<a target="_blank" href="http://poj.org/problem?id=2524">點選打開連結poj 2524</a>
水題
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8012272">點選檢視代碼</a>
第九題 poj 1456 Supermarket
<a target="_blank" href="http://poj.org/problem?id=1456">點選打開連結poj 1456</a>
思路: 貪心+并查集
1 題目的意思是給定n個物品的利潤和出售的最後時間，求最大的利潤
2 比較明顯的貪心問題，按照利潤排序，假設目前是第i個物品，那麼利潤為pi出售的時間為di，那麼假設di還沒有物品銷售那麼肯定先銷售第i個物品，否則找di～1這些時間裡面是否有沒有銷售物品
3 如果按照2的思路做法最壞的情況是O(n^2)，但是資料比較弱可以過。但是我們這邊可以利用并查集來優化，根據2如果di已經被占用了那麼我們要去找di～1的時間，這裡利用并查集的思路。如果di被占用了之後，那麼father[di] = di-1說明如果下次再來一個銷售日期為di的話是要放到di-1天，那麼對于第i個物品我們隻要判斷find(di)是不是大于0，如果是di可以放到find(di)這一天銷售，否則跳過
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9785381">點選檢視代碼</a>
第10題 poj 1733 Parity game
<a target="_blank" href="http://poj.org/problem?id=1733">點選打開poj 1733</a>
1 題目給定n個條件，要我們找到第一個不滿足條件的編号
2 每一個條件給的是區間[l,r]的1的奇偶數，很明顯[l,r]這個區間的1的個數可以由[0,r]-[0,l-1]得來
3 那麼我們利用并查集的思想，rank[x]表示的是x到跟節點這個區間即[x,father[x]]這個區間的1的個數，那麼奇偶性可以由1和0來表示
4 題目還有一個難點就是要離散化，一般的離散化的步驟是排序+去重，然後找的時候利用二分即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9811385">點選檢視代碼</a>
第十一題 poj 2912 Rochambeau
<a target="_blank" href="http://poj.org/problem?id=2912">點選打開poj 2912</a>
1 有n個小孩玩遊戲，裡面有一個入是裁判，剩下的人分為三組。現在我們既不知道裁判是誰也不知道分組的情況。現在n個小孩玩剪刀石頭布，已知每組的小孩隻會出同一種手勢，問誰是裁判
2 題目說了輸入=的時候說明是同一組，如果是<或>的時候說明是不同一組，那麼根據食物鍊那一題的思路，我們設rank[x]表示x和根節點的關系，如果是=那麼rank[x] = 0，如果是<則rank[x] = 1,否則為rank[x] = 2
3 剩下的就是怎麼求最少幾輪得到裁判的編号，要得出最後的裁判，也就是其他的人度不滿足的最大的那一輪，因為那一輪過後就能确定裁判了
4 判斷關系的時候，如果是不同的集合那就合并，否則判斷是否有rank[x] == (rank[y]+val)%3
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9842135">點選檢視代碼</a>
【hdu】
第一題 hdu 3038 How Many Answers Are Wrong
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3038">點選打開hdu 3038</a>
1 給定一序列的區間的和，求錯誤的個數
2 典型的帶權并查集，區間[l,r]的和等于sum[r]-sum[l-1]。對于一般涉及到區間和還有個數的問題的時候，都要把左下标減一來處理
3 用rank[x]表示的是x到跟節點的和即[x,find(x)]的和，那麼對于給定的x,y,val，fx為x的跟節點,fy為y的跟節點
如果fx != fy那麼這個時候就要考慮fx和fy的關系
fx > fy ，則father[fy] = fx; rank[fy] = rank[x]-val-rank[y];
fx < fy ，father[fx] = fy; rank[fx] = rank[y]+val-rank[x];
否則判斷rank[x]-rank[y]是否為val
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8020436">點選檢視代碼</a>
第二題 hdu 1856 More is better
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1856">點選打開連結hdu 1856</a>
思路: 離散化+并查集
1 點數最多為10^7，但是邊數最多10^5，是以我們必須采用離散化，然後利用帶權并查集的思想，rank[x]表示的是以x為根節點的集合的元素個數
2 這一題主要注意的就是當n = 0的時候，因為題目說了剛開始有10^7個人在房間裡面，是以n = 0的時候最多有一個人出去
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9871103">點選檢視代碼</a>
第三題 hdu 1198 Farm Irrigation
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1198">點選打開hdu 1198</a>
思路: 并查集
1 題目給定11快小方形，然後給定一個n*m的描述求n*m矩陣内的連通分量的個數
2 首先我們應該解決怎麼儲存11塊小方形，我們可以利用一個思維的分量來描述，比如A我們描述成{1,0,0,1}
3 那麼我們就可以做到線上進行并查集的操作，對于[i,j]這個方塊，它可能和[i-1,j]和[i,j-1]進行相連，那麼用i*m+j來唯一表示一個位置，那麼最後枚舉整個二維矩陣即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9877187">點選打開檢視代碼</a>
第四題 hdu 3635 Dragon Balls
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3635">點選打開hdu 3635</a>
1 題目說有n個城市每一個城市有一個龍珠編号為i，現在有m行的輸入包括兩種的情況
T x y 把x所在的集合的是以龍珠轉移到y集合上 Q x 詢問x所在集合的龍珠的個數
2 我們利用rank[x]表示的是根節點為x的集合的元素的個數，但是現在我們發現求轉移的次數不好求，剛開始我用的是一個vector數組來儲存，比如v[x]表示以x為根節點的集合的元素，那麼如果是把fx這個集合并到fy上的話，那麼我們枚舉v[fx]。但是這個方法TLE了
3 後來看了網上的題解，發現在求轉移次數的時候我們也可以利用遞歸合并的思想，比如把fx所在的集合轉移到fy的時候，那麼我們隻要把fx的轉移次數加一，那麼下次遞歸的時候我們在裡面進行處理即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9881055">點選檢視代碼</a>
第五題 hdu 2473 Junk-Mail Filter
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2473">點選打開hdu 2473</a>
分析：
1 題目初始化給定n個不同的點，然後給定m個操作，有兩種類型 m x y 表示x和y是同一種類型，s x表示把x從集合中單獨提前出來
2 這一題和uva11987很像，我們可以在初始化的時候把所有的節點的根節點設定成i+n, 那麼我們遇到提取x的時候就不會碰到x剛好是根節點的情況
3 在合并x和y的時候我們應該要考慮的問題是x和y是不是之前被提前過的，如果都不是那麼直接合并，否則我們應該注意合并的方向
4 遇到s x的時候我們把x的父親節點設為cnt，cnt是一個移動的數值，注意這裡cnt的值，數值應該要開大一點，這邊我WA了很多次
5 最後統計連通分量的個數即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9887083">點選打開檢視代碼</a>
第六題 hdu 3172 Virtual Friends
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3172">點選打開hdu 3172</a>
思路: 簡單并查集
1 利用map對每個人進行編号，然後利用并查集即可
2 這一題有個地方就是輸入case的時候要判斷不等于EOF
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9897847">點選打開檢視代碼</a>
第七題 hdu 3047 Zjnu Stadium
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3047">點選打開hdu 3047</a>
1 題目要求的是錯誤的條件的個數，這一題還是比較簡單的帶權并查集
2 我們用rank[x]表示的x到跟節點的距離，那麼對于x和y來說，如果x和y在不同集合那麼把x和y合并，否則直接判斷rank[x] == (rank[y]+val)%300
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8016291">點選檢視代碼</a>
第八題 hdu 2818 Building Block
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2818">點選打開hdu 2818</a>
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9900123">點選檢視代碼</a>
第九題 hdu 3461 Code Lock
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3461">點選打開hdu 3461</a>
思路: 并查集+離散化+快速幂
1 題目給定長度為n的字元串，然後給定m個操作，詢問最後的不同字元串的個數
2 考慮長度為n的時候，因為每個字元有26種情況('a'~'z')，是以有26^n。因為有m次的操作，題目中說了如果可以被變換那麼認為是相同的字元串，那麼不同的字元串就是所有不被操作區間的組合
3 那麼我們利用并查集去求有操作的集合的個數，比如[1,3],[3,5]和[1,5]是三個集合，而[1,3],[4,5]和[1,5]則是2個集合
4 對于區間[l,r]，那麼我們一般轉化為處理(l-1,r],這樣不用考慮端點的問題了，最後利用快速幂求出ans即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9903659">點選檢視代碼</a>
第十題 hdu 1558 Segment set
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1558">點選打開hdu 1558</a>
思路: 計算幾何+并查集
1 有n個操作，最後求有幾個集合或者說是連通分量
2 對于輸入一條線段我們就去前面找能夠和它相交的線段，利用并查集進行合并并且更新rank數組，rank[x]數組儲存的是以x為跟節點的集合的線段的數量
3 這一題難點就是線段的相交判斷
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9905143">點選打開檢視代碼</a>
【zoj】
第一題 zoj 3261 Connections in Galaxy War
<a target="_blank" href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3261">點選zoj 3261</a>
1 題目說的是有n個星球0~n-1，每個星球都有一個戰鬥值。n個星球之間有一些聯系，并且n個星球之間會有互相傷害
2 根本沒有思路的題，看了網上的思路才知道是逆向并查集。如果我們按照正常的并查集來做，以戰鬥值最大為根節點的話，當詢問的時候很容易，但是碰到删除邊的時候就很困難了，是以這裡才用逆向的并查集思路
3 我們先把所有的輸入儲存，然後我們可以這麼考慮，從後面往前面枚舉q次條件，如果是destroy我們認為是加邊，這樣的話就很好維護并查集了
4 但是這邊我們還要考慮初始的狀态，由于涉及到删邊而且不一定是删除所有的邊，是以我們隻要在m個關系裡面扣除要删除的邊，然後建立集合做為初始的狀态
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9857723">點選檢視代碼</a>
【uva】
第一題 uva 1160 X-Plosives
1 題目意思不難了解，一些化學物品由兩種元素組成，如果剛好有k個化學物品剛好由k個元素組成的話，那麼将會爆炸
2 k個化學物品剛好由k個元素組成，那麼等價于k條邊剛好由k的點組成，那麼這一題就變成判斷是否在同一個集合的問題了
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9490981">點選檢視代碼</a>
第二題 uva 1329 Corporative Network
1 給定兩種操作。I u v 是把節點u的父節點設為v ，并且節點u 和 節點v的節點距離為(|u-v|)%1000，E u詢問u到跟節點之間的距離
2 比較簡單的帶權并查集
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9491605">點選檢視代碼</a>
第三題 uva 11987 Almost Union-Find
1 題目給定三種操作，符合并查集的模式
2 但是有一種操作和普通的并查集不同的是，2 p q要把p并到q的集合，那麼這個時候p所在的集合就會發生變化，如果p剛好是它那個集合的跟節點那麼這個時候就要重新調整這個集合
3 那麼我們為了避免這種删除跟節點的情況出現，我們就把所有的i~n的節點的跟節點指向i+n，這樣保證了删除的時候肯定不會是根節點。這樣就變成了簡單的并查集問題了
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9720991">點選檢視代碼</a>
第四題 uva 12232 Exclusive-OR
思路: 并查集的擴充應用
1 題目給定三種指令，I p v表示Xp = v， I p q v表示Xp^Xq = v,
Q k Xp1 Xp2...Xpk求Xp1^Xp2^...^Xpk的值。
2 對于的異或的性質：1 a^0 = a，2 a^c^b^c = a^b，異或一個數偶數次等于沒有異或，因為異或偶數次的值為0，根據性質1那麼結果沒有影響
3 是以對于第一種指令I p v，我們可以虛拟出一個點Xn = 0，那麼p^xn = v，那麼第一和第二種指令我們可以統一成p^q = v的模式。
4 那麼我們設val[i] = Xi^Xfather[i]，但是要注意的是Xn要始終為那個集合的跟節點，因為這樣我們才能夠通過val[i]的值判斷Xi是否存在。
5 那麼Xp1^Xp2^...^Xpk = (val[Xp1]^val[Xp2]^...^val[Xpk])^(Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]);因為(val[Xp1]^val[Xp2]^...^val[Xpk])我們很容易求出來，是以我們現在就判斷Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]是否存在，根據性質2我們隻需要判斷父親節點出現次數為奇數的，如果父親節點為Xn，那麼值存在，否在不存在我們不能求出ans
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/9744161">點選檢視代碼</a>
![hdu 1272 小希的迷宮[kuangbin帶你飛]專題五 并查集
小希的迷宮[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)