并查集（思路加簡單例題）
并查集，顧名思義就是 合并集合，查找集合這兩個功能，
并查集一般是作用于連通性問題（可能是我太菜了）
首先我們看看并查集的查找，
舉個例子
小綠是小紅老大，小紅是小藍老大，小藍是小明老大，
那么小綠，小紅，小藍，小明，這四個人就因為誰是誰老大這個關系而連通
查找函式find（）查找與你連通的最上面一位//誰是你最大的老大
f[]陣列，用來儲存與你連通的上一位//誰是你的老大
比如 f[小明]=小藍，f[小藍]=小紅，f[小紅]=小綠
find[小明]=小綠，find[小藍]=小綠，find[小紅]=小綠；//歸根結底這些人的老大都是小綠
int f[maxn];
int find(int x)
{
if(x==f[x])
return x;
else
find(f[x]);
}//find函式
接下來，來看看合并函式join（）
今天的風兒甚是喧囂啊，果不其然，今天新來了伙人
這伙人里小a是小b的老大，小b是小c的老大，
那要想將這兩伙人合在一起，該怎么辦呢？
簡單，只需要讓他們認同一個人當老大就行了，（老大從小a和小綠里面隨便選一個都可以）
比如讓小a認小綠當老大，那么f[小a]=小綠，那么find（小b）=小綠；
這時候就需要用到join（）函式了
join函式就是將兩個集合合并,就是讓其中一個集合最大的老大認另外一個集合最大的老大作老大
void join(int x,int y)
{
int a=find(x);
int b=find(y);
if(a!=b)
f[a]=b;
}//這種有時會超記憶體，但不容易出錯
void join(int x,int y)
{
f[find(x)]=find(y);
}//這種不容易超記憶體，但有時候會出問題
一、模板題
https://www.acwing.com/problem/content/838/
一共有n個數，編號是1~n，最開始每個數各自在一個集合中，
現在要進行m個操作，操作共有兩種：
- “M a b”，將編號為a和b的兩個數所在的集合合并，如果兩個數已經在同一個集合中，則忽略這個操作；
- “Q a b”，詢問編號為a和b的兩個數是否在同一個集合中；
輸入格式
第一行輸入整數n和m，
接下來m行，每行包含一個操作指令，指令為“M a b”或“Q a b”中的一種，
輸出格式
對于每個詢問指令”Q a b”，都要輸出一個結果，如果a和b在同一集合內，則輸出“Yes”，否則輸出“No”，
每個結果占一行，
資料范圍
1≤n,m≤ 1 0 5 10^5 105
#include<bits/stdc++.h>
using namespace std;
int f[100006];
// 該函式的含義：查找a所在集合的祖先節點下標，從1開始, 并內部更新f[a]為a節點的祖先節點，
int find(int a)
{
// 根據通項公式，假設f[a]的祖先節點已知，
if (f[a] != a) f[a] = find(f[a]);
return f[a];
}
void join(int b,int c)
{
int x=find(b);
int y=find(c);
if(x!=y)
f[x]=y;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
// 初始化每個集合
for (int i = 1; i <= n; i++) f[i] = i;
int a, b;
char op[2];
while (m--)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') join(a,b);
else {
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
二、提高題
https://www.acwing.com/problem/content/242/
動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形，
A吃B， B吃C，C吃A，
現有N個動物，以1－N編號，
每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種，
有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：
第一種說法是”1 X Y”，表示X和Y是同類，
第二種說法是”2 X Y”，表示X吃Y，
此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的，
當一句話滿足下列三條之一時，這句話就是假話，否則就是真話，
1） 當前的話與前面的某些真的話沖突，就是假話；
2） 當前的話中X或Y比N大，就是假話；
3） 當前的話表示X吃X，就是假話，
你的任務是根據給定的N和K句話，輸出假話的總數，
輸入格式
第一行是兩個整數N和K，以一個空格分隔，
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類，
若D=1，則表示X和Y是同類，
若D=2，則表示X吃Y，
輸出格式
只有一個整數，表示假話的數目，
資料范圍
1≤N≤50000
0≤K≤100000
輸入樣例：
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.并查集(拓展域)//一般有多種關系的，都可以用拓展域，
這道題目我們主要是要開三個拓展的域,也就是同類域（1，n）,捕食域（n+1，2n）,以及天敵域（2n+1,3n）.
即f[x]表示同類的關系，f[x+n]表示捕食關系，f[x+2n]表示天敵關系
如果x,y是同類,但是x的捕食域有y,那么錯誤
如果x,y是同類,但是x的天敵域有y,那么錯誤
如果x是y的天敵,但是x的同類域中有y,那么錯誤
如果x是y的天敵,但是x的天敵域中有y,那么錯誤
2.帶權并查集（下面有進行介紹）
在這個題中相對關系就是食物鏈上的關系，因此帶權并查集中的權值就應該記錄兩個動物在食物鏈上的相對關系，A->B為0表示同類，為1表示A吃B，為2表示A被B吃，這個值不同于前面兩個題中的區間合、分數差，它是不可以直接累加的，要考慮三個問題：
1.路徑壓縮時，如何更新Value
如果現在有A->B為1，B->C為1，怎么求A->C？顯然A吃B，B吃C，那么由題意C應該吃A，那么A->C應該為2；
如果現在有A->B為2，B->C為2，怎么求A->C？顯然B吃A，C吃B，那么由題意A應該吃C，那么A->C應該為1；
如果現在有A->B為0，B->C為1，怎么求A->C？顯然A、B同類，B吃C，那么由題意A應該吃C，那么A->C應該為1；
找規律不難發現，A->C = (A->B + B->C) % 3，因此關系值的更新需要累加再模3，
2.區間合并時，如何更新Value
由1不難發現，本題的Value更新無非就是多了個取模操作，因此不難驗證區間合并的更新操作應該為：
value[px] = (-value[x] + value[y] + s)%3;//s表示x和y之間的關系
拓展域代碼
#include<bits/stdc++.h>
using namespace std;
int f[200005];
int d,x,y;
int n,k,sum=0;
int find(int a)
{
if(a==f[a])
return a;
else
find(f[a]);
}
void join(int a,int b)
{
f[find(a)]=find(b);
}
int main()
{
cin>>n>>k;
for(int i=1;i<=3*n;i++)
f[i]=i;
while (k--)
{
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)
sum++;
else
{
if(d==1)
{
if(find(x)==find(y+n)||find(x)==find(y+n+n))//如果x是在y的捕食域或者y的天敵域內就說明是錯誤的
sum++;
else
{
join(x,y);//表示x和y是同類
join(x+n,y+n);//x和y是同類，那么x和y的捕食域一樣
join(x+n+n,y+n+n);//x和y的天敵域一樣
}
}
else
{
if(x==y||find(x)==find(y+n)||find(x)==find(y))//表示x等于y，x在y的捕食域，x和y是同類，三種情況
sum++;
else
{
join(x+n,y);//y在x的捕食域
join(x,y+n+n);//x在y的天敵域
join(x+n+n,y+n);//x的天敵是在y的捕食域內
}
}
}
}
cout<<sum<<endl;
return 0;
}
三、帶權并查集(合并和查找都得更新權值)
每一條邊都記錄了每個節點到根節點的一個權值，這個權值該設為什么由具體的問題而定，一般都是兩個節點之間的某一種相對的關系，但是考慮到權值就會有兩個問題：
1.每個節點都記錄的是與根節點之間的權值，那么在Find的路徑壓縮程序中，權值也應該做相應的更新，因為在路徑壓縮之前，每個節點都是與其父節點鏈接著，那個Value自然也是與其父節點之間的權值
2.在兩個并查集做合并的時候，權值也要做相應的更新，因為兩個并查集的根節點不同，
下面就來看在這兩個程序中，如何更新權值：
int find(int x)
{
if (x != f[x])
{
int t = f[x];
f[x] = find(f[x]);//路徑壓縮
value[x] += value[t];
}
return parent[x];
}
可以看到更新權值只多了兩行代碼，先記錄下原本父節點的編號，因為在路徑壓縮后父節點就變為根節點了，再將當前節點的權值加上原本父節點的權值，此時父節點的權值已經是父節點到根節點的權值了，因此加上這個權值就會得到當前節點到根節點的權值，
合并：
int px = find(x);
int py = find(y);
if (px != py)
{
f[px] = py;
value[px] = -value[x] + value[y] + s;//s表示x和y之間的關系
}
可以將他看成向量的加減，
HihoCoder-1515-分數調查
描述
小Hi的學校總共有N名學生，編號1-N，學校剛剛進行了一場全校的古詩文水平測驗，
學校沒有公布測驗的成績，所以小Hi只能得到一些小道訊息，例如X號同學的分數比Y號同學的分數高S分，
小Hi想知道利用這些訊息，能不能判斷出某兩位同學之間的分數高低？
輸入
第一行包含三個整數N, M和Q，N表示學生總數，M表示小Hi知道訊息的總數，Q表示小Hi想詢問的數量，
以下M行每行三個整數，X, Y和S，表示X號同學的分數比Y號同學的分數高S分，
以下Q行每行兩個整數，X和Y，表示小Hi想知道X號同學的分數比Y號同學的分數高幾分，
對于50%的資料，1 <= N, M, Q <= 1000
對于100%的資料，1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000
資料保證沒有矛盾，
輸出
對于每個詢問，如果不能判斷出X比Y高幾分輸出-1，否則輸出X比Y高的分數，
樣例輸入
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
樣例輸出
-1
20
0
#include<bits/stdc++.h>
using namespace std;
const int maxN = 100005;
int f[maxN];
int score[maxN];
int find(int x)
{
if (x != f[x])
{
int t = f[x];
f[x] = find(f[x]);
score[x] += score[t];
}
return f[x];
}
int main()
{
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1 ; i <= n ; i ++ )
{
f[i] = i;
}
while ( m-- )
{
int x, y, s;
scanf("%d%d%d", &x, &y, &s);
int px = find(x);
int py = find(y);
if (px != py)//合并
{
f[px] = py;
score[px] = -score[x] + score[y] + s;
}
}
while (q --)
{
int x, y;
scanf("%d%d",&x,&y);
if (find(x) != find(y))
{
printf("-1\n");
}
else {
printf("%d\n", score[x] - score[y]);
}
}
return 0;
}
(int i = 1 ; i <= n ; i ++ )
{
f[i] = i;
}
while ( m-- )
{
int x, y, s;
scanf("%d%d%d", &x, &y, &s);
int px = find(x);
int py = find(y);
if (px != py)//合并
{
f[px] = py;
score[px] = -score[x] + score[y] + s;
}
}
while (q --)
{
int x, y;
scanf("%d%d",&x,&y);
if (find(x) != find(y))
{
printf("-1\n");
}
else {
printf("%d\n", score[x] - score[y]);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/201603.html
標籤：其他
下一篇：概率dp習題