并查集

概念：
并查集是一種資料結構
一般由兩個函式 F i n d ( ) Find( ) Find()、 U n i o n ( ) Union( ) Union()和陣列 f [ ] f[] f[]構成，
f [ ] f[] f[]用來記錄自己的根
函式 f i n d ( x ) find(x) find(x)用于查找 x x x的根，函式 U n i o n ( x , y ) Union(x, y) Union(x,y)用于合并兩個集，

例子的引入 ：）

背景：

在一個百家爭戰(鳴)的時代，存在非常多的家派，比如說：武當派， 少林派， 華山派······
因為當時時代極為不和平，所以不是屬于一個家派的人見到面就會干架(社會不良行為)
但是可能會遇到一些問題，（可能會誤傷隊友，
關系網如圖

關系好復雜·······
這個時候，就可以用并查集來儲存關系，
Such as：馬真的師傅是沖虛道長，沖虛道長的師傅是張三豐，··········

F i n d ( ) Find() Find()函式的引入

當馬真遇到陸菲青，
馬真問道：“敢問閣下可否與鄙人一戰？”
陸菲青反問：“敢問閣下是哪個家派的？鄙人所屬武當派，”
為了防止發生誤傷，
馬真使用了 F i n d ( ) Find( ) Find()函式， 來查詢自己的根，

inline int Find(int x) {				//查找x的家派
	while(f[x] != x)			//如果x的師父是x自己， 那么自己就是家派
		x = f[x];				//x接著找他的上級，直到找到家派為止
	return x;					//家派駕到~~~
}

但是······，馬真–>沖虛道長–>張三豐–>武當派，問的人也太多了，而且時間也挺慢的···
（說不定還沒問到，已經打完了 ）
于是，便出現了一種更為快捷的 F i n d ( ) Find() Find()函式，名為 路徑壓縮 ，

inline int Find(int x) {  //inline進行優化
	if (f[x] == x) return x;    //如果x的師傅是x自己
	else return f[x] = find(f[x]);  //如果不是，那么繼續自己的師傅
}

經過了路徑壓縮， 關系的儲存就會變成以下形式：

可以直接找到自己所屬家派，避免誤傷，挺好的，

U n i o n ( ) Union() Union()函式的引入

亂世之下，華山派部分弟子的關系變的愈發惡劣，經常出現矛盾，
終于，弟子風清揚忍無可忍，
用 U n i o n ( ) Union() Union()投靠了武當派，
于是關系：

U n i o n ( ) 函 數 的 模 板 ： Union()函式的模板： Union()函數的模板：

inline void Union(int x, int y) {	   //inline優化
	int t1 = Find(x), t2 = Find(y);    //尋找x的師父和y的師父
	if (t1 != t2) f[t2] = t1;		   //y認x做師父，兩個集合合并成一個
	return;
}

關于并查集，還有一個關鍵的地方，就是 初始化

void init() {
	for (int i = 1; i <= n; i++)
		f[i] = i; //在沒有認師之前，都是自學的，自己就是自己的師父，即自己就是自己的根
	return;
} 

下面是模板題的引入：

P3367 【模板】并查集

題目描述

如題，現在有一個并查集，你需要完成合并和查詢操作，

輸入格式

第一行包含兩個整數 N N N， M M M，表示共有 N N N個元素和 M M M個操作，
接下來 M M M行，每行包含三個整數 Z i , X i , Y i Z_i,X_i,Y_i Zi?,Xi?,Yi?，
當 Z i = 1 Z_i = 1 Zi?=1時，將 X i X_i Xi?和 Y i Y_i Yi?所在的集合合并，
當 Z i = 2 Z_i = 2 Zi?=2時，輸出 X i X_i Xi?與 Y i Y_i Yi?是否在同一個集合內，是的輸出 Y Y Y ；否則輸出 N N N，

輸出格式

對于每一個 Z i = 2 Z_i = 2 Zi?=2的操作，都有一行輸出，每行包含一個大寫字母，為 Y Y Y或者 N N N，

說明/提示

對于 30 % 30\% 30%的資料， N ≤ 10 ， M ≤ 20 N≤10，M≤20 N≤10，M≤20.，
對于 70 % 70\% 70%的資料， N ≤ 100 ， M ≤ 1 0 3 N≤100，M≤10^3 N≤100，M≤103，
對于 100 % 100\% 100%的資料， 1 ≤ N ≤ 1 0 4 , 1 ≤ M ≤ 2 × 1 0 5 1≤N≤10^4,1≤M≤2×10^5 1≤N≤104,1≤M≤2×105，

輸入樣例

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

輸出樣例

N
Y
N
Y

題目分析：模板題，套模板
C o d e Code Code

#include <bits/stdc++.h>
using namespace std;

int n, m;
int f[100050];

void init() {  //初始化
	for (int i = 1; i <= n; i++)
		f[i] = i;
}

inline int Find(int x) {  //找“根”
	if (f[x] == x) return x;
	else return f[x] = Find(f[x]);
} 

inline void Union(int x, int y) {  //合并集合
	int t1 = Find(x), t2 = Find(y);
	if (t1 != t2) f[t1] = t2;		
}

inline void Check(int x, int y) {  //檢查條件
	int t1 = Find(x), t2 = Find(y);
	if (t1 == t2) puts("Y");  //比printf還要快的函式，而且還會自動換行，但是只能參考 char 型別的變數
	else puts("N");  //更快，更靚，更強！！！
}

int main() {
	scanf("%d%d", &n, &m);
	init();
	while (m--) {
		int z, x, y;
		scanf("%d%d%d", &z, &x, &y);  
		if (z == 1) Union(x, y);
		else Check(x, y); 
	}
	return 0;  //完美結束
}

并查集的擴展域：

基本概念：

有些情況下，元素不只含有一個屬性，傳遞的關系也不只一種，因此我們可以將每個元素拆成多個元素，在合并的時候維護關系的傳遞性，通過擴展出來的屬性來維護傳遞性，
是不是聽起來很麻煩 ，但說白了就是把原來的集合擴大幾倍，然后在新的集合中建立關系，

P2024 [NOI2001]食物鏈

題目描述：

動物王國中有三類動物 A , B , C A,B,C A,B,C，這三類動物的食物鏈構成了有趣的環形， A A A 吃 B B B， B B B 吃 C C C， C C C 吃 A A A，
現有 N 個動物，以 1 － N 編號，每個動物都是 A,B,C 中的一種，但是我們并不知道它到底是哪一種，
有人用兩種說法對這 N 個動物所構成的食物鏈關系進行描述：
●第一種說法是 1 X Y，表示 X X X 和 Y Y Y 是同類，
●第二種說法是 2 X Y，表示 X X X 吃 Y Y Y ，
此人對 N 個動物，用上述兩種說法，一句接一句地說出 K 句話，這 K 句話有的是真的，有的是假的，
當一句話滿足下列三條之一時，這句話就是假話，否則就是真話，
判斷假話的條件
●當前的話與前面的某些真的話沖突，就是假話，
●當前的話中 X X X 或 Y Y Y 比 N N N 大，就是假話，
●當前的話表示 X X X 吃 X X X，就是假話，
你的任務是根據給定的 N 和 K 句話，輸出假話的總數，

輸入格式：
第一行兩個整數 N ， K N，K N，K，表示有 N N N 個動物， K K K 句話，
第二行開始每行一句話（按照題目要求，見樣例），

輸出格式：
一行，一個整數，表示假話的總數，

輸入樣例：

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

輸出樣例：

3

提示：
1 ≤ N ≤ 5 ? 1 0 4 1 ≤ N ≤ 5 ? 10^4 1≤N≤5?104，
1 ≤ K ≤ 1 0 5 1 ≤ K ≤ 10^5 1≤K≤105，

決議：
這道題需要保存三種關系，分別是：同類，獵物，天敵，
所以可以擴展并查集， 從 n n n 變成 3 × n 3 × n 3×n ，
①用 x x x 表示 x x x的同類，
②用 x + n x + n x+n 表示 x x x的獵物，
③用 x + 2 × n x + 2 × n x+2×n表示 x x x的天敵，
假話的判斷如題所示，即為所求
那么，
當 d = 1 d=1 d=1且這句話是真話時，
d = 1 時 { U n i o n ( x , y ) ( x 和 y 是 同 類 ) U n i o n ( x + n , y + n ) ( x 的 獵 物 和 y 的 獵 物 是 同 類 ) U n i o n ( x + 2 ? n , y + 2 ? n ) ( x 的 天 敵 和 y 的 天 敵 是 同 類 ) d = 1 時 \left\{ \begin{matrix} Union(x, y) (x和y是同類) \\ Union(x + n, y + n) (x的獵物和y的獵物是同類)\\ Union(x + 2 * n, y + 2 * n)(x的天敵和y的天敵是同類)\\ \end{matrix} \right. d=1時????Union(x,y)(x和y是同類)Union(x+n,y+n)(x的獵物和y的獵物是同類)Union(x+2?n,y+2?n)(x的天敵和y的天敵是同類)?
當 d = 2 d=2 d=2且這句話時真話時，
d = 2 時 { U n i o n ( x , y + 2 ? n ) ( x 是 y 的 天 敵 ) U n i o n ( x + n , y ) ( x 的 獵 物 是 y ) U n i o n ( x + 2 ? n , y + n ) ( x 的 天 敵 是 y 的 獵 物 ) d = 2 時 \left\{ \begin{matrix} Union(x, y + 2 * n)(x是y的天敵)\\ Union(x + n, y)(x的獵物是y)\\ Union(x + 2 * n, y + n)(x的天敵是y的獵物)\\ \end{matrix} \right. d=2時????Union(x,y+2?n)(x是y的天敵)Union(x+n,y)(x的獵物是y)Union(x+2?n,y+n)(x的天敵是y的獵物)?
C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;

int ans;
int n, k;
int f[150005];

void init() {  //擴展域的初始化
	for (int i = 1; i <= 3 * n; i++) {
		f[i] = i;
	}
}

inline int Find(int x) {   //找根
	if (f[x] == x) return x;
	else return f[x] = Find(f[x]);
}

inline void Union(int x, int y) {  //合并集合
	int t1 = Find(x), t2 = Find(y);
	if (t1 != t2) f[t2] = t1;
}

inline bool check1(int x, int y) {  //判斷是否為同類
	if (Find(x + n) == Find(y) || Find(x + 2 * n) == Find(y)) 
		return true;
	else
	    return false;
}

inline bool check2(int x, int y) {  //判斷是否為獵物
	if (Find(x) == Find(y) || Find(x + 2 * n) == Find(y))
		return true;
	else 
		return false;
}

int main() {
	scanf("%d%d", &n, &k);
	init();
	while (k--) {
		int d, x, y;
		scanf("%d%d%d", &d, &x, &y);
		if (x > n || y > n) {ans++; continue;}
		switch(d) {  //聽說比if快一點
			case 1:	
				if (check1(x, y)) {ans++; continue;}
				else {
					Union(x, y);
					Union(x + n, y + n);
					Union(x + 2 * n, y + 2 * n);
				}
				break;
			case 2:
				if (check2(x, y)) {ans++; continue;}
				else {
					Union(x, y + 2 * n);
					Union(x + n, y);
					Union(x + 2 * n, y + n);
				}
				break;
		}
	}
	return !printf("%d", ans);//又省了一行
}

完結
（本篇博客將會持續更新）