說(shuō)明：

學(xué)習(xí)該模板比較推薦洛谷P3367 【模板】并查集，以下是該題鏈接及描述：
https://www.luogu.org/problemnew/show/P3367

題目描述

如題，現(xiàn)在有一個(gè)并查集，你需要完成合并和查詢操作。

輸入格式：

第一行包含兩個(gè)整數(shù)N、M，表示共有N個(gè)元素和M個(gè)操作。
接下來(lái)M行，每行包含三個(gè)整數(shù)Zi、Xi、Yi
當(dāng)Zi=1時(shí)，將Xi與Yi所在的集合合并
當(dāng)Zi=2時(shí)，輸出Xi與Yi是否在同一集合內(nèi)，是的話輸出Y；否則話輸出N

輸出格式：

如上，對(duì)于每一個(gè)Zi=2的操作，都有一行輸出，每行包含一個(gè)大寫字母，為Y或者N

輸入樣例#1：

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

輸出樣例#1：

N
Y
N
Y

說(shuō)明

時(shí)空限制：1000ms,128M

數(shù)據(jù)規(guī)模：

對(duì)于30%的數(shù)據(jù)，N<=10，M<=20；
對(duì)于70%的數(shù)據(jù)，N<=100，M<=1000；
對(duì)于100%的數(shù)據(jù)，N<=10000，M<=200000。

提示：

要抓住每個(gè)元素的父親，合理應(yīng)用路徑壓縮：查找完根節(jié)點(diǎn)后，在遞歸回來(lái)時(shí)順便將路徑上的元素的父親指向根節(jié)點(diǎn)。代碼不長(zhǎng)的。

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define N 1000001 using namespace std; int f[N],n,m; int find(int k) {if(k!=f[k]) f[k]=find(f[k]);return f[k]; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&z,&x,&y);x=find(x);y=find(y);if(z==1&&x!=y) f[x]=y;if(z==2){if(x==y) printf("Y\n");else printf("N\n");}}return 0; }

相關(guān)鏈接：

C++模板小站：
https://blog.csdn.net/zj_mrz/article/details/80950647

C++快速冪模板：
https://blog.csdn.net/zj_mrz/article/details/80950616

C++高精度減法模板：
https://blog.csdn.net/zj_mrz/article/details/80965324

C++高精度乘法模板：
https://blog.csdn.net/zj_mrz/article/details/80967394

轉(zhuǎn)載于:https://www.cnblogs.com/zj-mrz/p/10122458.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的C++并查集模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。