嗯...

?

題目鏈接：https://www.luogu.org/problemnew/show/P3367

?

并查集可以支持的操作：“并”和“查”。然后這道題主要就是考察這兩種操作。將每一個點的“父親”初始化為自己，然后分別進行“并”和“查”。

“并”：用遞歸函數find來查找每一個點的父節點。然后將其中一個父節點設為另一個父節點的父親即可。

“查”：用遞歸函數find來查找每一個點的父節點。判斷父節點是否相同即可。

?

AC代碼：

1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 int f[100005]; 7 int x, y, z; 8 9 inline int find(int x){ 10 if(f[x] != x) 11 f[x] = find(f[x]); 12 return f[x]; 13 }//遞歸求父節點，即"查" 14 15 int main(){ 16 int n, m; 17 scanf("%d%d", &n, &m); 18 for(int i = 1; i <= n; i++) f[i] = i; 19 for(int i = 1; i <= m; i++){ 20 scanf("%d%d%d", &z, &x, &y); 21 if(z == 1){ 22 int r1 = find(x); 23 int r2 = find(y); 24 f[r1] = r2; 25 } 26 else if(z == 2){ 27 int r1 = find(x); 28 int r2 = find(y); 29 if(r1 == r2) printf("Y\n"); 30 else printf("N\n"); 31 } 32 } 33 return 0; 34 } AC代碼

?

轉載于:https://www.cnblogs.com/New-ljx/p/10846793.html

總結

以上是生活随笔為你收集整理的洛谷 P3367 【模板】并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。