本人小蒻蒟，做了一些并查集的題目，理解不深，但是還是想寫一下關于并查集，可以用來以后回看（嘻嘻~）
帶權我不會，請翻書，或者看大佬博客
并查集
據我個人理解呢，就是合并和查找集合
合并很簡單，就是把兩個集合合并在起，如圖中將x，y集合合并（圖爛見諒）
我們可以把兩個集合分別看為一個家族，合并就是將y作為x的爸爸，也就是x下的所有孩子的祖宗變為為y，
而查找一般就是查每一個元素的根節點（也就是祖宗，我習慣稱為找祖宗hhh），我們需要一步一步往上尋找直到找到祖宗為止，
首先呢，我們需要對每個元素的爸爸初始化，讓每個元素獨立為營
int fa[N];
for(int i = 0;i < n;i ++) fa[i] = i;
然后我們寫找祖宗的函式
int find(int x){
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
在這個代碼模板中，fa[N]這個陣列存的是x的父輩，如果x的祖宗不是x我們就進行遞回處理，找x的爸爸的祖宗，一直遞回~直到我們沒有辦法繼續往上查找時，我們也就找到了x的祖宗！！！
這個find函式我認為需要重點理解一下，因為遞回其實還蠻難的，可能是因為我菜
認真思考后會發現，我們的find函式還有一個神奇的功能，那就是路徑壓縮，寫出這個代碼的大佬很牛，佩服哇！
那么路徑壓縮是什么意思呢？看圖（好丑）
到這里呢，就是我目前了解的并查集，還有一些祖宗拖家帶口合并的（很2的題），那樣就把小的家族并到大的家族
并查集例題
先簡簡單單入門題
題目
規定：x和y是親戚，y和z是親戚，那么x和z也是親戚，如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚，
輸入
第一行：三個整數n,m,p，（n<=5000,m<=5000,p<=5000），分別表示有n個人，m個親戚關系，詢問p對親戚關系，
以下m行：每行兩個數Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有親戚關系，
接下來p行：每行兩個數Pi，Pj，詢問Pi和Pj是否具有親戚關系，
輸出
P行，每行一個’Yes’或’No’，表示第i個詢問的答案為“具有”或“不具有”親戚關系，
輸入例子
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
輸出
Yes
Yes
No
讀完題，我們也可以看出來，這完全就是一個并查集的題目
比較簡單，我就直接放代碼了
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,p;
int fa[5010];
//找祖宗函式
int find(int x){
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
int main(){
scanf("%d %d %d",&n,&m,&p);//n個人m個親戚關系 詢問p對親戚關系
for(int i = 0;i < n;i ++) fa[i] = i;//他爹初始化
while(m--){
int a,b;
scanf("%d %d",&a,&b);
if(find(a) != find(b)) fa[find(a)] = find(b);//親戚合并
}
while(p--){//這個回圈就是判斷是否為親戚
int i,j;
scanf("%d %d",&i,&j);
if(find(i) == find(j)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
是不是很簡單呢？我們再來一個模板題加深印象
題目
一共有n個數，編號是1~n，最開始每個數各自在一個集合中，
現在要進行m個操作，操作共有兩種：
1、“M a b”，將編號為a和b的兩個數所在的集合合并，如果兩個數已經在同一個集合中，則忽略這個操作；
2、“Q a b”，詢問編號為a和b的兩個數是否在同一個集合中；
輸入
第一行輸入整數n和m，
接下來m行，每行包含一個操作指令，指令為“M a b”或“Q a b”中的一種，
輸出
對于每個詢問指令”Q a b”，都要輸出一個結果，如果a和b在同一集合內，則輸出“Yes”，否則輸出“No”，
每個結果占一行，
輸入樣例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
輸出
Yes
No
Yes
嗯！直接放代碼，代碼塊上會有相關解釋
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n,m;
int p[N];
int find(int x){//找祖宗函式
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++) p[i] = i;//他爹初始化 嘻嘻~
while(m--){
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
//根據題意判斷是合并集合還是查找
if(op[0] == 'M') p[find(a)] = find(b);
else{
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
這道題就是簡單的模板題了，我覺得對理解并查集這個東西很有用，可能是難的題我看不懂
下邊看兩道有點思考程度的簡單并查集，可能對于大佬來說一看就會~
The Suspects
題目
在一所大學里有n個學生（這些學生的編號為0～n?1），這些學生由于興趣愛好等原因組成了m個群體，
由于非典（SARS）流行，該大學的學生會需要排除可能的非典患者，
由于非典傳染性強，學生會的成員假定：如果一個群體中有一個人是非典患者，那么這個群體中的所有人都是非典患者，
現在已知編號為0的學生為非典患者，請你找出這些學生中非典患者的人數，
輸入
輸入資料由多組資料組成，
每組資料包括m+1行：
第1行有兩個由空格隔開的非負整數n和m，其意義如題目所述，
第2～m+1行表示每個群體的人員資訊，每行的第一個數字k表示該群體的人數，其后有k個用空格隔開的非負整數，表示這個群體的各個成員的編號，
當n=m=0時，表示輸入結束，不需要處理之后的資料，
輸出
對于每組輸入資料，輸出一個整數，表示這組資料中非典患者的數量，每組資料的輸出以換行符結尾，
輸入樣例
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
輸出
4
1
1
這道題呢，大致意思可以理解為，有很多集合，集合里有的有相同元素，我們需要合并一些集合，并把含有0的集合里的元素個數輸出出來，
簡單的合并和查找處理
int p,x;
scanf("%d",&p);//學生人數
scanf("%d",&x);//第一個學生編號
j = find(x);//用j存第一個學生編號的祖宗~
for(int i = 1;i < p;i ++){
scanf("%d",&x);
q[find(x)] = j;//讓每一個學生的祖宗的父輩都是第一個學生的祖宗~
}
這個里面，讓每一個學生的祖宗的父輩都是第一個學生的祖宗就是，合并操作，可以再紙上演算一下這個程序，就可以加深理解
int p = find(0);//用p存編號為0的學生的祖宗
for(int i = 0;i < n;i ++){
if(find(i) == find(0)) cnt++;//如果編號為i的學生和編號為0是同一個祖宗cnt就加一
}
printf("%d\n",cnt);
cnt = 0;
}
這個就是查找的時候的靈活應用了
代碼
#include <iostream>
using namespace std;
const int N = 30010;
int n,m,j,cnt;
int q[N];
int find(int x){
if(q[x] != x) q[x] = find(q[x]);
return q[x];
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n == 0 && m == 0) break;
for(int i = 0;i < n;i ++) q[i] = i;//初始化
while(m--){
int p,x;
scanf("%d",&p);//學生人數
scanf("%d",&x);//第一個學生編號
j = find(x);//用j存第一個學生編號的祖宗~
for(int i = 1;i < p;i ++){
scanf("%d",&x);
q[find(x)] = j;//讓每一個學生的祖宗的父輩都是第一個學生的祖宗~
}
}
int p = find(0);//用p存編號為0的學生的祖宗
for(int i = 0;i < n;i ++){
if(find(i) == find(0)) cnt++;//如果編號為i的學生和編號為0是同一個祖宗cnt就加一
}
printf("%d\n",cnt);
cnt = 0;
}
return 0;
}
下面是一道全英文題目
Wireless Network
題目
An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B.
In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.
輸入
The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:
- “O p” (1 <= p <= N), which means repairing computer p.
- “S p q” (1 <= p, q <= N), which means testing whether computer p and q can communicate.
The input will not exceed 300000 lines.
輸出
For each Testing operation, print “SUCCESS” if the two computers can communicate, or “FAIL” if not.
輸入樣例
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
輸出樣例
FAIL
SUCCESS
題意：首先輸入n個電腦的位置和每臺電腦的信號覆寫半徑d，剛開始電腦都是壞的，你需要去維修，
O表示修復一臺電腦
S檢查是否可以聯通，通過另一臺電腦間接聯通也可以
只有修理好的才可以進行通信，如果兩臺計算機的距離不超過d，則兩臺電腦之間可以通信，
這個題就需要我們很靈活的處理，只有修復并且可以通信的電腦我們才將他們合并
int q[M];//存父輩
double x[M],y[M];//計算機坐標
int z[M];//修復好的電腦
int c[M][M];//記錄距離小于等于d的兩臺電腦
在這道題中 c[M][M] 陣列和 z[M] 的加入就是我們對這道題的靈活處理
for(int i = 1;i <= N;i ++)//算出兩個計算機的距離并判斷是否小于d，若小于，記錄兩個計算機，
for(int j = i;j <= N;j ++){
if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d){
c[i][j] = c[j][i] = 1;//記錄 可以聯通的計算機
}
}
我們先預處理可以聯通的電腦，并把它存下來
scanf("%d",&a);
z[a] = 1;
當輸入O的時候，我們把維修的電腦激活，用z[M]記錄下來，以便于后邊的判斷，
if(i != a && z[a] == 1 && z[i] == 1&& c[i][a] == 1){//判斷計算機是否被修過，然后和可以連通的計算機合并
if(find(a) != find(i)) q[find(a)] = find(i); //合并為一個集合
}
判斷，這個電腦和另一個電腦可以聯通，并且都被維修過，我們就將兩個電腦合并
整體代碼如下
#include <iostream>
using namespace std;
const int M = 1010;
int N,d;
int q[M];//存他爹
double x[M],y[M];//計算機坐標
int z[M];//修復好的電腦
int c[M][M];//記錄距離小于等于d的兩臺電腦
int find(int x){
if(q[x] != x) q[x] = find(q[x]);
return q[x];
}
int main(){
int a[M];
char op[2];
scanf("%d %d",&N,&d);
for(int i = 1;i <= N;i ++) q[i] = i;
for(int i = 1;i <= N;i ++) scanf("%lf %lf",&x[i],&y[i]);
for(int i = 1;i <= N;i ++)//算出兩個計算機的距離并判斷是否小于d，若小于，記錄兩個計算機，
for(int j = i;j <= N;j ++){
if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d){
c[i][j] = c[j][i] = 1;//記錄 可以聯通的計算機
}
}
getchar();//清除空格
while(~scanf("%s",op)){
int a,b;
if(op[0] == 'O'){
scanf("%d",&a);
z[a] = 1;
for(int i = 1;i <= N;i ++){
if(i != a && z[a] == 1 && z[i] == 1&& c[i][a] == 1){//判斷計算機是否被修過，然后和可以連通的計算機合并
if(find(a) != find(i)) q[find(a)] = find(i); //合并為一個集合
}
}
}else{
scanf("%d %d",&a,&b);
if(find(a) == find(b)) printf("SUCCESS\n");
else printf("FAIL\n");
}
getchar();
}
return 0;
這個題給我的啟發就是，關于并查集的一些靈活運用，當然也是在熟悉模板之后的，
并查集目前我就理解了這么點點，我才是個剛接觸編程不久的小蒟蒻，嘻嘻~
帶權并查集太難了以后有機會一定寫（可能明年叭）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/230333.html
標籤：其他
上一篇：SpringBoot日期格式轉換