- 【用途】並查集是一種資料結構，用於處理不相交集合(Disjoint Sets)的合併及查詢。操作時使用Union-Find algorithm。
- 【原理】
- 資料結構：有向圖
- 每個點有一個出邊(out-degree) 代表每個頂點所屬集合的「代表元素」，初始值指向自己。
- 查詢時如果遇到指向自己的點 x，則 x 即為該集合的代表元素，回傳 x，否則繼續查詢。
- 【實作1】
- 初始化陣列 p[i] = i，表示指向自己。
- Find( )：找出目標元素屬於哪一個集合 。【版本2】 順便進行路徑壓縮(邊的縮減)，可縮短後續查詢的時間。
- Union( )：把兩個集合合併成一個。
- 【實作2】 可連帶查詢集合的成員數目
- 初始化陣列 p[i] = -1，表示指向自己。
- p[代表元素] = 集合內的成員數目(負數)。
- 當 i 不是所屬集合的代表元素時，p[i] = 代表元素編號。
- 【範例】ZeroJudge a445: 新手訓練系列- 我的朋友很少
- 【範例】ZeroJudge d831: 畢業旅行
- 【練習】ZeroJudge d449: 垃圾信件
【實作1】
//版本-1
int Find(int x){
// 當p[x] = x，x 即為該所屬集合的代表元素
// 否則遞迴繼續找
return p[x] == x ? x : Find(p[x]);
}
//版本-2: 路徑壓縮
int Find(int x){
// 當p[x] = x，x 即為該所屬集合的代表元素
// 否則遞迴繼續找，順便做「路徑壓縮」
return p[x] == x ? x : p[x] = Find(p[x])
}
void Union(int x,int y){
int g1 = Find(x); //找出x所屬集合的代表元素
int g2 = Find(y); //找出y所屬集合的代表元素
if(g1 != g2) p[g2] = g1; //將g2指向g1，即為合併兩個集合，g1為代表元素
}
【實作2】可連帶查詢集合的成員數目
int Find(int x){
// 初始值 p[x] = -1 表示指向自己
return p[x] < 0 ? x : p[x] = Find(p[x]);
}
void Union(int x, int y){
int g1 = Find(x);
int g2 = Find(y);
if(g1 != g2){
p[g1] += p[g2]; //加總元素個數(負值)
p[g2] = g1; //p[]:只有代表元素的值是存元素個數，其它的存代表元素編號
}
}