【基礎演算法】並查集
- 2020 年 6 月 5 日
- 筆記
- 【C/C++】【鞭長駕遠】從入門到喜愛
合併集合
一共有n個數，編號是1~n，最開始每個數各自在一個集合中。
現在要進行m個操作，操作共有兩種：
- 「M a b」，將編號為a和b的兩個數所在的集合合併，如果兩個數已經在同一個集合中，則忽略這個操作；
- 「Q a b」，詢問編號為a和b的兩個數是否在同一個集合中；
輸入格式
第一行輸入整數n和m。
接下來m行，每行包含一個操作指令，指令為「M a b」或「Q a b」中的一種。
輸出格式
對於每個詢問指令」Q a b」，都要輸出一個結果，如果a和b在同一集合內，則輸出「Yes」，否則輸出「No」。
每個結果佔一行。
數據範圍
1≤n,m≤1051≤n,m≤105
輸入樣例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
輸出樣例：
Yes
No
Yes
思路：
此題運用的是並查集演算法，合併和查詢集合。將兩個集合合併只需將一個的根結點連接到另一個根節點上就行，查詢就是訪問根節點是否相同。
程式碼：
#include<iostream> #include<cstdio> using namespace std; const int N = 100010; int p[N]; int find(int x) {//查找根結點 if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { int n, m; 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; }
