淺談并查集
LaTeX \LaTeX LATEX
傳送門
定義
并查集是一種樹形的資料結構，它可以用于維護多個不相交集合的合并、查詢操作。并查集通常以森林的形式維護。我們通常将每個集合看作是一棵有根樹。
基本操作
合并
對于每次合并元素 ( x , y ) (x, y) (x,y) 所在的集合的請求，我們分别找到 x , y x, y x,y 所在的有根樹的根節點，并将 x x x 的根節點父節點置為 y y y 的根節點。
若我們需要動态查詢合并後 x x x 所在的集合的大小，則合并時 x x x 所在的集合大小需要加上 y y y 所在的集合大小，即 s i z e [ x ] + = s i z e [ y ] size[x] += size[y] size[x]+=size[y] 。
查詢
對于每次查詢元素 ( x , y ) (x, y) (x,y) 是否在同一集合中的請求，我們分别找到 x , y x, y x,y 所在的有根樹的根節點。由于同一集合内，所有元素所在的有根樹的根節點相同，故而我們隻需要判斷 x x x 的根節點是否等于 y y y 的根節點即可。
路徑壓縮
對于每次查找 x x x 的祖宗結點，時間複雜度為 O ( h ) O(h) O(h) ，而我們可以查找完成後指派，時間複雜度為 O ( 1 ) O(1) O(1) 。
初始化
對于任意 1 < = i < = n ， f a [ i ] = 1 ， s i z e [ i ] = 1 1 <= i <= n，fa[i] = 1，size[i] = 1 1<=i<=n，fa[i]=1，size[i]=1 。
并查集模闆（洛谷 P3367）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int u, v, fa[maxn];
//查詢 + 優化
int get(int x){
if (fa[x] == x)return x;
return fa[x] = get(fa[x]);//路徑壓縮
}
//合并
void merge(int x, int y){
x = get(x);
y = get(y);
if (x != y)
fa[y] = x;
}
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)fa[i] = i;
for (int i = 1; i <= m; i++){
scanf("%d%d", &u, &v);
merge(u, v);
}
for (int i = 1; i <= k; i++){
scanf("%d%d", &u, &v);
if (get(u) == get(v))printf("Yes\n");
else printf("No\n");
}
return 0;
}
種類并查集
轉載自 知乎 @Pecco
一般的并查集，維護的是具有連通性、傳遞性的關系，例如親戚的親戚是親戚。但是，有時候，我們要維護另一種關系：敵人的敵人是朋友。種類并查集就是為了維護一種循環對稱的關系而誕生的。
洛谷 P1525 關押罪犯
題目描述
S S S 城現有兩座監獄，一共關押着 N N N 名罪犯，編号分别為 1 − N 1−N 1−N。他們之間的關系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則随時可能爆發沖突。我們用“怨氣值”（一個正整數值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為 c c c 的罪犯被關押在同一監獄，他們倆之間會發生摩擦，并造成影響力為 c c c 的沖突事件。
每年年末，警察局會将本年内監獄中的所有沖突事件按影響力從大到小排成一個清單，然後上報到 S S S 城 Z Z Z 市長那裡。公務繁忙的 Z Z Z 市長隻會去看清單中的第一個事件的影響力，如果影響很壞，他就會考慮撤換警察局長。
在詳細考察了 N N N 名罪犯間的沖突關系後，警察局長覺得壓力巨大。他準備将罪犯們在兩座監獄内重新配置設定，以求産生的沖突事件影響力都較小，進而保住自己的烏紗帽。假設隻要處于同一監獄内的某兩個罪犯間有仇恨，那麼他們一定會在每年的某個時候發生摩擦。
那麼，應如何配置設定罪犯，才能使 Z Z Z 市長看到的那個沖突事件的影響力最小？這個最小值是多少？
輸入格式
每行中兩個數之間用一個空格隔開。第一行為兩個正整數 N , M N,M N,M，分别表示罪犯的數目以及存在仇恨的罪犯對數。接下來的 M M M 行每行為三個正整數 a j , b j , c j a_j,b_j,c_j aj,bj,cj ，表示 a j a_j aj 号和 b j b_j bj 号罪犯之間存在仇恨，其怨氣值為 c j c_j cj 。
資料保證 1 < a j ≤ b j ≤ N , 0 < c j ≤ 1 0 9 1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9 1<aj≤bj≤N,0<cj≤109 ，且每對罪犯組合隻出現一次。
輸出格式
共 1 1 1 行，為 Z Z Z 市長看到的那個沖突事件的影響力。如果本年内監獄中未發生任何沖突事件，請輸出 0 0 0。
其實很容易想到，這裡可以貪心，把所有沖突關系從大到小排個序，然後盡可能地把沖突大的犯人關到不同的監獄裡，直到不能這麼做為止。這看上去可以用并查集維護，但是有一個問題：我們得到的資訊，不是哪些人應該在相同的監獄，而是哪些人應該在不同的監獄。這怎麼處理呢？這個題其實有很多做法，但這裡，我們介紹使用種類并查集的做法。
我們開一個兩倍大小的并查集。例如，假如我們要維護4個元素的并查集，我們改為開8個機關的空間：
我們用 1 ∼ 4 1 \sim 4 1∼4 維護朋友關系（就這道題而言，是指關在同一個監獄的獄友），用5~8維護敵人關系（這道題裡是指關在不同監獄的仇人）。現在假如我們得到資訊： 1 1 1 和 2 2 2 是敵人，應該怎麼辦？
我們
merge(1, 2+n), merge(1+n, 2)
。這裡 n n n 就等于4，但我寫成 n n n 這樣更清晰。對于 1 1 1 個編号為 i i i 的元素， i + n i+n i+n 是它的敵人。是以這裡的意思就是： 1 1 1 是 2 2 2 的敵人， 2 2 2 是 1 1 1 的敵人。
現在假如我們又知道 2 2 2 和 4 4 4 是敵人，我們
merge(2, 4+n), merge(2+n, 4)
;
發現了嗎，敵人的敵人就是朋友， 2 2 2 和 4 4 4 是敵人， 2 2 2 和 1 1 1 也是敵人，是以這裡， 1 1 1 和 4 4 4 通過 2 + n 2+n 2+n 這個元素間接地連接配接起來了。這就是種類并查集工作的原理。
A C c o d e AC \ code AC code
#include<bits/stdc++.h>
using namespace std;
int read() //快速讀入，可忽略
{
int ans = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
ans = (ans << 3) + (ans << 1) + c - '0';
c = getchar();
}
return ans;
}
struct data //以結構體方式儲存便于排序
{
int a, b, w;
} C[100005];
int cmp(data &a, data &b)
{
return a.w > b.w;
}
int fa[40005], rank[40005]; //以下為并查集
int find(int a)
{
return (fa[a] == a) ? a : (fa[a] = find(fa[a]));
}
int query(int a, int b)
{
return find(a) == find(b);
}
void merge(int a, int b)
{
int x = find(a), y = find(b);
if (rank[x] >= rank[y])
fa[y] = x;
else
fa[x] = y;
if (rank[x] == rank[y] && x != y)
rank[x]++;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
rank[i] = 1;
fa[i] = i;
}
}
int main()
{
int n = read(), m = read();
init(n * 2); //對于罪犯i，i+n為他的敵人
for (int i = 0; i < m; ++i)
{
C[i].a = read();
C[i].b = read();
C[i].w = read();
}
std::sort(C, C + m, cmp);
for (int i = 0; i < m; ++i)
{
if (query(C[i].a, C[i].b)) //試圖把兩個已經被标記為“朋友”的人标記為“敵人”
{
printf("%d\n", C[i].w); //此時的怒氣值就是最大怒氣值的最小值
break;
}
merge(C[i].a, C[i].b + n);
merge(C[i].b, C[i].a + n);
if (i == m - 1) //如果循環結束仍無沖突，輸出0
puts("0");
}
return 0;
}