![TOC]
并查集操作的復(fù)雜度是log n。是一個(gè)衰減非常快的函數(shù)慌洪，即使n 很大，log n的結(jié)果也接近一個(gè)常數(shù)凑保，不會(huì)超過5冈爹。
其實(shí)并查集顧名思義就是有“合并集合”和“查找集合中的元素”兩種操作的關(guān)于數(shù)據(jù)結(jié)構(gòu)的一種算法。
A case of its application
有n個(gè)人欧引，每個(gè)人都有唯一的標(biāo)簽频伤，分別是0,1,……,n – 1。已知0號(hào)得了一種傳染病芝此，這種病只要與人接觸了就會(huì)傳染憋肖，一傳十十傳百。我們統(tǒng)計(jì)了哪些人有過接觸婚苹，求最終被感染的人是哪些岸更？
假設(shè)我們給出的接觸信息如下：
[[0, 1], [0, 2], [1, 3], [3, 4], [1, 2], [5, 4]]
先合并
最后查找0所在的集合
Other applications
2、用在求解最小生成樹的Kruskal算法里租副。
初始化坐慰、查找、合并
初始化存儲(chǔ)空間（array or struct）
一般來說用僧，題目簡(jiǎn)單用數(shù)組结胀，題目復(fù)雜用結(jié)構(gòu)體，因?yàn)榻Y(jié)構(gòu)體有條理责循，數(shù)組可以少打幾個(gè)字糟港。
包括對(duì)所有單個(gè)的數(shù)據(jù)建立一個(gè)單獨(dú)的集合（即根據(jù)題目的意思自己建立的最多可能有的集合，為下面的合并查找操作提供操作對(duì)象）
在每一個(gè)單個(gè)的集合里面院仿，有三個(gè)東西秸抚。
1，集合所代表的數(shù)據(jù)歹垫。（這個(gè)初始值根據(jù)需要自己定義剥汤，不固定）
2，這個(gè)集合的層次通常用rank表示（一般來說排惨，初始化的工作之一就是將每一個(gè)集合里的rank置為0）吭敢。
3，這個(gè)集合的類別parent（有的人也喜歡用set表示）（其實(shí)就是一個(gè)指針暮芭，用來指示這個(gè)集合屬于那一類鹿驼，合并過后的集合，他們的parent指向的最終值一定是相同的辕宏。）
（**有的簡(jiǎn)單題里面集合的數(shù)據(jù)就是這個(gè)集合的標(biāo)號(hào)畜晰，也就是說只包含2和3，1省略了）瑞筐。
初始化的時(shí)候凄鼻，一個(gè)集合的parent都是這個(gè)集合自己的標(biāo)號(hào)。沒有跟它同類的集合聚假，那么這個(gè)集合的源頭只能是自己了块蚌。
（最簡(jiǎn)單的集合就只含有這三個(gè)東西了，當(dāng)然魔策，復(fù)雜的集合就是把3指針這一項(xiàng)添加內(nèi)容匈子，如PKU食物鏈那題，我們還可以添加enemy指針闯袒，表示這個(gè)物種集合的天敵集合虎敦；food指針，表示這個(gè)物種集合的食物集合政敢。隨著指針的增加其徙，并查集操作起來也變得復(fù)雜，題目也就顯得更難了）
結(jié)構(gòu)體表示法
有的人是建立一個(gè)結(jié)構(gòu)體把集合表示出來喷户，如：
#define MAX 10000
struct Node
{
int data;
int rank;
int parent;
}node[MAX];
數(shù)組表示法
有的人則是弄很多相同大小的數(shù)組唾那，如：
int set[max];//集合index的類別，或者用parent表示
int rank[max];//集合index的層次褪尝，通常初始化為0
int data[max];//集合index的數(shù)據(jù)類型
//初始化集合
void Make_Set(int i)
{
set[i]=i;//初始化的時(shí)候闹获，一個(gè)集合的parent都是這個(gè)集合自己的標(biāo)號(hào)期犬。沒有跟它同類的集合，那么這個(gè)集合的源頭只能是自己了避诽。
rank[i]=0;
}
一般來說龟虎，題目簡(jiǎn)單用數(shù)組，題目復(fù)雜用結(jié)構(gòu)體沙庐，因?yàn)榻Y(jié)構(gòu)體有條理鲤妥，數(shù)組可以少打幾個(gè)字。
Find without PathCompression : 查看某個(gè)元素在不在集合中拱雏，返回parent代表元
就是找到parent指針的源頭棉安，可以把函數(shù)命名為get_parent（或者find_set，這個(gè)隨你喜歡铸抑，以便于理解為主）
如果集合的parent等于集合的編號(hào)（即還沒有被合并或者沒有同類）贡耽，那么自然返回自身編號(hào)。
如果不同（即經(jīng)過合并操作后指針指向了源頭（合并后選出的rank高的集合））那么就可以調(diào)用遞歸函數(shù)羡滑，如下面的代碼：
/**
*查找集合i（一個(gè)元素是一個(gè)集合）的源頭（遞歸實(shí)現(xiàn)）菇爪。
如果集合i的父親是自己，說明自己就是源頭柒昏，返回自己的標(biāo)號(hào)凳宙；
否則查找集合i的父親的源頭。
**/
int get_parent(int x)
{
if(node[x].parent==x)
return x;
return get_parent(node[x].parent);
}
數(shù)組的話就是：
//查找集合i（一個(gè)元素是一個(gè)集合）的源頭（遞歸實(shí)現(xiàn)）
int Find_Set(int i)
{
//如果集合i的父親是自己职祷，說明自己就是源頭氏涩，返回自己的標(biāo)號(hào)
if(set[i]==i)
return set[i];
//否則查找集合i的父親的源頭
return Find_Set(set[i]);
}
Union
這就是所謂并查集的并了。至于怎么知道兩個(gè)集合是可以合并的有梆，那就是題目的條件了是尖。
先看代碼：
void Union(int a,int b)
{
a=get_parent(a);
b=get_parent(b);
if(node[a].rank>node[b].rank)
node[b].parent=a;
else
{
node[a].parent=b;
if(node[a].rank==node[b].rank)
node[b].rank++;
}
}
再給出數(shù)組顯示的合并函數(shù)：
void Union(int i,int j)
{
i=Find_Set(i);
j=Find_Set(j);
if(i==j) return ;
if(rank[i]>rank[j]) set[j]=i;
else
{
if(rank[i]==rank[j]) rank[j]++;
set[i]=j;
}
}
Union工作原理
每次做Union操作的時(shí)候都需要先做find操作，然后再合并兩個(gè)集合的祖先泥耀；K次union操作最多涉及2k個(gè)元素(假設(shè)每次做union操作的兩個(gè)元素術(shù)語(yǔ)不同的集合)
至少需要n-1次union才能把所有元素都合并成一個(gè)n元素的大集合饺汹。也就是說，每次union操作以后痰催，集合的數(shù)據(jù)最多減少一個(gè)（這里可以注意一下:因?yàn)橹蟮囊坏李}就會(huì)用到這個(gè)理論）
Union Optimal
Path Compression通過更改查找部分的代碼實(shí)現(xiàn)
parent[x] = find(parent[x]); //路徑壓縮
控制樹的高度來降低復(fù)雜度
一般來說兜辞，在union操作的時(shí)候，我們有兩個(gè)原則：
a. Link by size：節(jié)點(diǎn)較少的合并到節(jié)點(diǎn)多的夸溶；
b. Union by rank：高度較低的樹合并到高度較高的樹逸吵。
這兩個(gè)優(yōu)化的原理都是通過控制樹的高度來降低復(fù)雜度的，因?yàn)閒ind的時(shí)間復(fù)雜度取決于樹的高度缝裁。
Exercise
小試牛刀
Longest Consecutive Sequence
大展身手
Number of Islands
http://dwz.cn/39Y5PD
