【模板】并查集
from luogu P3367
時間限制 ：1s
記憶體限制：125M
題目描述：
如題，現在有一個并查集，你需要完成合并和查詢操作，
輸入格式：
第一行包含兩個整數 N,M ,表示共有 N 個元素和 M 個操作，
接下來 M 行，每行包含三個整數 Zi,Xi,Yi，
當 Zi=1 時，將 Xi 與 Yi 所在的集合合并，
當 Zi=2時，輸出 Xi 與 Yi 是否在同一集合內，是的輸出 Y ；否則輸出 N
輸出格式：
對于每一個 Zi=2 的操作，都有一行輸出，每行包含一個大寫字母，為 Y 或者 N ，
樣例輸入：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
樣例輸出：
N
Y
N
Y
說明/提示：
對于 100% 的資料，0 < N <= 10 ^ 4，1 0 < M <= 2 * 10 ^ 5，
這是一道并查集很基礎的題目，就直接上代碼吧！
AC代碼：
#include<iostream>
using namespace std;
int father[10005]; //記錄每個節點的所在樹的代表節點，也可以理解為該點的父節點
int z,x,y,fx,fy;
int find(int &x){
if(father[x] == x)
return x;
return father[x] = find(father[x]);
}
int main() {
int n, m;
cin>>n>>m;
for(int i = 1;i <= n;++i) father[i] = i; //初始化每個點的父親為其本身
while(m--) {
cin >> z >> x >> y;
fx = find(x), fy = find(y); //找到x和y的father
if (z == 1) {
if (fx != fy)
father[fx] = fy; //如果z=1那么合并x和y所在的樹
} else {
if (fx == fy) cout << "Y\n";
else cout << "N\n"; //否則輸出x和y是否在同一棵樹
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256439.html
標籤：其他
上一篇：前端開發：專案運行npm install 提示XXX packages are looking for funding run `npm fund` for details的解決方法