一位衩、關(guān)于并查集
1.1 并查集概念引入
并查集，顧名思義熔萧，就是合并查詢集合糖驴，是一種特殊的樹狀數(shù)據(jù)結(jié)構(gòu)。一般是用來解決元素分組的問題佛致，或是管理一些不相交的集合贮缕，他支持兩種操作：1.合并（Union）2.查詢（Find），比較典型的問題就是找親戚,最小生成樹的Kruskal算法等等,我們可以考慮使用并查集進(jìn)行維護(hù)俺榆。感昼。
并查集的主要思想是用一個(gè)集合中的元素來代表這個(gè)集合。
這么說可能有點(diǎn)抽象罐脊，有人用武俠的例子來生動(dòng)刻畫了這個(gè)并查集定嗓，有興趣可以了解一下 鏈接在這.
簡(jiǎn)單來說，就是有一堆不認(rèn)識(shí)的人萍桌，他們需要拉幫結(jié)派宵溅，這里需要解決兩個(gè)問題，第一上炎，怎么讓他們結(jié)盟（合并）层玲，第二，怎么知道他們是不是同一個(gè)幫派（查詢）
1.2 合并
根據(jù)這幾張圖可以感受一下他們是怎么樣建立關(guān)系的
初始狀態(tài)下大家都是分散的反症，各自成一派辛块，所以自己的教主都是自己
后面2和3想加入1的幫派，于是將他們的教主設(shè)為1铅碍，這樣我就只要知道他們教主是誰润绵，就知道他們是不是這幫派的人
5 6和4同盟
4又和1同盟了，那么大家全都是一家人胞谈，英文我們的教主都是1尘盼，咱們的頭是一樣的，那肯定是一幫子人烦绳。
最后的樹結(jié)構(gòu)是這樣的
另外提一下卿捎，這里的教主比較專業(yè)的叫法是生成元。我們并查集就是通過生成元來判斷是不是隸屬于這個(gè)集合的
1.3 查詢
我們已經(jīng)知道了他們?cè)趺丛谕粋€(gè)集合里的径密，不就是看他們的教主嘛午阵，那我查他們是不是一路子人，就看他們教主是不是一樣的就可以了。
那現(xiàn)在的主要問題就是怎么知道他的教主底桂。
剛剛最后的圖樣很明顯植袍，是一個(gè)樹形的數(shù)據(jù)結(jié)構(gòu)，我們通過訪問其上一級(jí)（引入pre數(shù)組訪問）籽懦，訪問到最上面的一層以后肯定能找到教主的于个。所以我們很自然想到的方法就是遞歸。
直接上代碼暮顺。
二厅篓、代碼實(shí)現(xiàn)
初始化（每個(gè)人就是一個(gè)幫派，自己的教主就是自己本身）
void init(int num)
{
//一開始是盤散沙捶码，每個(gè)人都是各立一派贷笛，
//所以自立為王，他們的上一級(jí)（pre）就是他們自己
for (int i = 1; i <= num; i++)
{
pre[i] = i;
}
}
找生成元（遞歸思想）
int find(int key)
{
if (pre[key] == key)
return key;
return find(pre[key]);
}
合并
void unite(int x, int y)
//并查集中的‘并’函數(shù)
//就是讓x,y結(jié)成同盟（讓x,y的老大都是一樣的）
//即隸屬于同一個(gè)集合內(nèi)
{
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y)
return;
else{
pre[root_x] = root_y;
}
}
三宙项、一些優(yōu)化
3.1 查詢路徑壓縮
我們希望我們只要找到最后的教主就好了乏苦，但是每一輪我都這樣遞歸訪問，明顯會(huì)有點(diǎn)麻煩尤筐，具體如圖汇荐。
那有沒有解決問題的辦法呢？答案是有的盆繁，要解決遞歸引起的問題掀淘，我們就在遞歸上下點(diǎn)功夫，我們是否能將最后遞歸找到的教主油昂，賦值給每一個(gè)之前遞歸過程中的元素呢革娄？那我們多一個(gè)賦值操作就行了,后續(xù)我訪問的時(shí)候，至少這些訪問過的節(jié)點(diǎn)可以一步到位直接訪問到教主冕碟，這就是那些大佬們總是說的路徑壓縮拦惋。
int find(int key)
//并查集中的’查‘函數(shù)
//找教主，要是不是自己的話安寺，就遞歸往上找
//這邊是優(yōu)化了一下算法厕妖，在遞歸過程中又賦值一下
//只要查過了一次老大后面就只要調(diào)用一次就能找到老大（root）了
{
if (pre[key] == key)
return key;
return pre[key] = find(pre[key]);
}
厲害一點(diǎn)的可以直接一行三元運(yùn)算符?: 的代碼搞定
return x == fa[x] ? x : (fa[x] = find(fa[x]));
3.2 合并路徑壓縮（按秩合并）
那樣優(yōu)化以后，大家普遍會(huì)有一個(gè)認(rèn)識(shí)誤區(qū)挑庶，并查集最終生成的樹深度是2言秸，但是要注意路徑壓縮只在查詢時(shí)進(jìn)行，也只壓縮一條路徑迎捺，所以并查集最終的結(jié)構(gòu)仍然可能是比較復(fù)雜的
在合并問題上举畸，我們也可以留意一下，之前合并的操作的時(shí)候凳枝，或許你會(huì)想著一個(gè)問題抄沮，為什么要委屈x，讓他的幫主上一級(jí)變成y的幫主，讓y的幫主的上一級(jí)變成x的幫主不行嗎合是？其實(shí)是可以的，合理的變锭环，在路徑上甚至還會(huì)有所優(yōu)化聪全。這是大佬們說的并查集按秩合并。
觀察這個(gè)圖可以發(fā)現(xiàn)辅辩，樹的深度變小了难礼，這意味著訪問教主所要遞歸的次數(shù)變少了。具體我們應(yīng)該把深度小的樹合并到深度大的樹上去玫锋，這樣合并以后蛾茉，到根節(jié)點(diǎn)距離變長的節(jié)點(diǎn)個(gè)數(shù)會(huì)更少。
代碼上需要做的改變是
這里我們引入一個(gè)Rank數(shù)組撩鹿，記錄每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的深度
初始化的時(shí)候我們做一點(diǎn)改變谦炬，剛開始的深度是1
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
合并操作代碼優(yōu)化
void unite(int x, int y)
{
int root_x = find(x);
int root_y = find(y);
//已經(jīng)是同一個(gè)集合的話就不需要做了
if (root_x == root_y)
return;
//小樹并大樹
if (depth[root_x] > depth[root_y])
pre[root_y] = root_x;
else
{
if (depth[root_x] == depth[root_y])
depth[y]++;
pre[root_x] = root_y;
}
}
這里只有一種情況是要改變樹的深度的，那就是當(dāng)兩棵樹的深度相同時(shí)节沦，深度要加1键思。小數(shù)并大樹的時(shí)候，深度還是大樹的深度甫贯。不會(huì)變的
請(qǐng)看吼鳞，這是兩個(gè)樹深度相同的情況
插入到另外一組樹后，深度會(huì)+1叫搁，因?yàn)椴迦氲臉渖厦骓斨徊鍢涞母?jié)點(diǎn)赔桌，所以深度多了一，倒過來插也是一樣的渴逻。
四疾党、題目試煉
2017年第八屆 藍(lán)橋杯C組 C/C++決賽 合根植物
題目描述
w星球的一個(gè)種植園，被分成 m * n 個(gè)小格子（東西方向m行惨奕，南北方向n列）仿贬。每個(gè)格子里種了一株合根植物。
這種植物有個(gè)特點(diǎn)墓贿，它的根可能會(huì)沿著南北或東西方向伸展茧泪，從而與另一個(gè)格子的植物合成為一體。
如果我們告訴你哪些小格子間出現(xiàn)了連根現(xiàn)象聋袋，你能說出這個(gè)園中一共有多少株合根植物嗎队伟？
輸入格式
第一行，兩個(gè)整數(shù)m幽勒，n嗜侮，用空格分開，表示格子的行數(shù)、列數(shù)（1<m,n<1000）锈颗。
接下來一行顷霹，一個(gè)整數(shù)k，表示下面還有k行數(shù)據(jù)(0<k<100000)
接下來k行击吱，第行兩個(gè)整數(shù)a淋淀，b，表示編號(hào)為a的小格子和編號(hào)為b的小格子合根了覆醇。
格子的編號(hào)一行一行朵纷，從上到下，從左到右編號(hào)永脓。
比如：5 * 4 的小格子袍辞，編號(hào)：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
樣例輸入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
樣例輸出
5
其合根情況參考下圖：
我的AC代碼附上~
#include <stdio.h>
const int MAX_N = 1000005;
int pre[MAX_N], depth[MAX_N];
int m, n, x, y, T,sum;
void init(int num)
{
//一開始是盤散沙，
//每個(gè)人都是各立一派常摧，所以自立為王搅吁，
//他們的上一級(jí)（pre）就是他們自己
for (int i = 1; i <= num; i++)
{
pre[i] = i;
depth[i] = 0;
}
}
int find(int key)
//并查集中的’查‘函數(shù)
//找教主，要是不是自己的話落午，就遞歸往上找似芝，
//這邊是優(yōu)化了一下算法，在遞歸過程中又賦值一下板甘，
//只要查過了一次老大后面就只要調(diào)用一次就能找到老大（root）了
{
if (pre[key] == key)
return key;
return pre[key] = find(pre[key]);
}
void unite(int x, int y)
//并查集中的‘并’函數(shù)
//就是讓x,y結(jié)成同盟（讓x,y的老大都是一樣的）
//即隸屬于同一個(gè)集合內(nèi)
{
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y)
return;
if (depth[root_x] > depth[root_y])
pre[root_y] = root_x;
else
{
if (depth[root_x] == depth[root_y])
depth[y]++;
pre[root_x] = root_y;
}
}
int main()
{
// freopen("1.in", "r", stdin);
// freopen("2.out", "w", stdout);
scanf("%d %d", &m, &n);
scanf("%d", &T);
init(m * n);
while(T--){
scanf("%d %d", &x, &y);
unite(x, y);
}
for (int i = 1; i <= m * n; i++)
{
if (find(i) == i)
{
sum++;
}
}
printf("%d\n", sum);
return 0;
}
后續(xù)關(guān)注更新~~~~
