提起并查集，相信各位dalao并不陌生，甚至那就2行的板子已經(jīng)被你們玩爛了……

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，它常用于處理一些不相交集合的合并及查詢問題，而最常見也是最簡單的問題就是找親戚：

有1，2，3，4，5這么幾個人，告訴你兩個人是不是親戚，之后詢問兩個人的關(guān)系。

比如知道1，3是親戚，3，4是親戚，起初要把每個點所在集合的代表初始化為其自身，隨后合并1，3所在集合和3，4所在集合，那么隨后詢問時我們會知道1，4在同一集合，是親戚。

這就是簡單的并查集的應用，它形成的是一個森林，就是使用樹來表示集合，樹的每個節(jié)點就表示集合中的一個元素，樹根的元素就是該集合的代表。而對于給定的元素，可以很快的找到這個元素所在的集合是什么，以及合并兩個元素所在的集合，從而實現(xiàn)了對于任意兩個元素是否在同一集合的判斷。

并查集還有常見的兩種優(yōu)化，一是路徑壓縮，二是啟發(fā)式合并。第一種是幾乎必用的，第二種主要應對充滿惡意的非隨機數(shù)據(jù)，絕大多數(shù)情況下可以不用。

1 class Union_Find_Set { 2 private: 3 const int maxn = 500000 + 10; 4 int p[maxn]; //每個元素所在集合的代表 5 public: 6 inline void Refl(int x) { for(int i=1; i<=x; ++i) p[i] = i; } //初始化 7 int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); } //查詢所在集合 8 inline void Unio(int x, int y) { p[ Find(x) ] = Find(y); } //合并兩個集合 9 }

?

這個東西真的有用嗎？能吃嗎？答案是肯定的。

這是個很方便的數(shù)據(jù)結(jié)構(gòu)，它每個操作的時間都是接近常數(shù)時間的，可以被用于求最小生成樹，聯(lián)通子圖，以及最近公共祖先等等。

而它還可以人為地搞一個幾倍大小的補集用于維護元素的其它關(guān)系。

?在做一個并查集時，我們將空間開到幾倍大小，用第一段（1~n）與第二段（n+1~2*n），第三段……之間的聯(lián)系維護元素與元素不同的關(guān)系，很明顯，p[i] 與 p[n+i]，p[2*n+i]……將擁有不同的意義，而這也就是補集的意義與方便之處。在實際應用中的做法已經(jīng)顯而易見，只需要倍開空間，記住自己對每一段給他的意義，然后實現(xiàn)代碼就好。

一道例題：Luogu P2024

題目描述

動物王國中有三類動物 A,B,C，這三類動物的食物鏈構(gòu)成了有趣的環(huán)形。A 吃 B，B吃 C，C 吃 A。

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

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

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

第二種說法是“2 X Y”，表示 X 吃 Y 。

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

? 當前的話與前面的某些真的話沖突，就是假話

? 當前的話中 X 或 Y 比 N 大，就是假話

? 當前的話表示 X 吃 X，就是假話

你的任務是根據(jù)給定的 N 和 K 句話，輸出假話的總數(shù)。

輸入輸出格式

輸入格式：

第一行兩個整數(shù)，N，K，表示有 N 個動物，K 句話。

第二行開始每行一句話（按照題目要求，見樣例）

輸出格式：

一行，一個整數(shù)，表示假話的總數(shù)。

輸入輸出樣例

輸入樣例#1： 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 輸出樣例#1：
3

說明

1 ≤ N ≤ 5 ? 10^4

1 ≤ K ≤ 10^5

這是一道毫無修飾的，利用并查集補集完成的題目。而且由于只有3種動物，我們很方便地可以開3倍空間，用第一段表示種類，第二段表示其食物，第三段表示其天敵，關(guān)系就一目了然了。

見代碼：

1 #include <cstdio> 2 #include <cctype> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 50000 + 10; 8 int n, k, p[3 * maxn], ans; 9 10 inline void Refl(int x) { for(int i=1; i<=3*x; ++i) p[i] = i; } 11 int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); } 12 inline void Unio(int x, int y) { p[ Find(x) ] = Find(y); } 13 14 inline void read(int &x) { 15 register char ch = 0; x = 0; 16 while( !isdigit(ch) ) ch = getchar(); 17 while( isdigit(ch) ) x = (x*10) + (ch^48), ch = getchar(); 18 } 19 20 int main(int argc, char const *argv[]) 21 { 22 scanf("%d%d", &n, &k); 23 int ques, a, b; Refl(n); 24 while( k-- ) { 25 read(ques), read(a), read(b); 26 if( a>n || b>n ) { ++ans; continue; } 27 if( ques==1 ) 28 if( Find(n+a)==Find(b) || Find(n+b)==Find(a) ) ++ans; 29 /* 如果存在a吃b或者b吃a的關(guān)系，那他們不是一種動物 */ 30 else Unio(a, b), Unio(n+a, n+b), Unio(2*n+a, 2*n+b); 31 /* 否則把他們的三種屬性全關(guān)聯(lián)起來 */ 32 else 33 if( Find(a)==Find(b) || Find(a)==Find(n+b) ) ++ans; 34 /* 如果已知a和b是同種動物或者是b吃a的關(guān)系，這句話是假話 */ 35 else Unio(n+a, b), Unio(a, 2*n+b), Unio(2*n+a, n+b); 36 /* 否則是真話，按照捕食關(guān)系關(guān)聯(lián)起來 */ 37 /* 因為只有三種動物，所以如果a吃b，則a是b的天敵且被b的食物吃 */ 38 } 39 printf("%d\n", ans); 40 return 0; 41 }

暫時寫到這里好了，以后想起什么詳細的解釋再補充w。

?

　　　　　　　　　　　　　　　　　　　　　　　　　—— 信じてた 今でさえ believe in 願う。

轉(zhuǎn)載于:https://www.cnblogs.com/nanjoqin/p/9069133.html

總結(jié)

以上是生活随笔為你收集整理的并查集及其补集应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。