AcWing 836. 合并集合
【題目描述】

在查看解析之前，先給自己一點時間思考哦！

【題解】
并查集是一種用于處理集合合并與查詢問題的數據結構，通常支持以下兩種操作：
Find：查詢一個元素所在的集合。
Union：將兩個元素所在的集合合并為一個集合。

為了提高效率，常用以下優化：
路徑壓縮：在find操作時，將訪問路徑上的每個節點直接指向根節點，從而加速后續查詢。
【參考代碼】

#include <iostream>
using namespace std;const int N = 1e5 + 10;  // 最大集合數為 10^5
int p[N];  // 用于存儲每個元素的父節點
int n, m;  // n 為集合數，m 為操作數// 查找操作：返回元素 x 所在集合的根
int find(int x) {if(p[x] != x)  // 如果 p[x] 不是 x，說明 x 不是根節點p[x] = find(p[x]);  // 路徑壓縮，將 x 直接指向根節點return p[x];  // 返回根節點
}int main() {cin >> n >> m;  for(int i = 1; i <= n; i++)  // 初始化時，每個元素自成一組p[i] = i;while(m--) { string op;  int a, b;  cin >> op >> a >> b;if(op == "M")  // 如果是 M 操作，合并 a 和 b 所在的集合p[find(a)] = find(b);  // 將 a 和 b 合并else {  // 如果是 Q 操作，查詢 a 和 b 是否在同一個集合if(find(a) == find(b))  // 如果 a 和 b 的根節點相同，則在同一個集合cout << "Yes" << endl;elsecout << "No" << endl;  // 否則不在同一個集合}}return 0;
}