并查集的基础题目--http://acm.hdu.edu.cn/showproblem.php?pid=1213；
并查集基础代码：
void inis_set(int n) { // 对数组进行初始化 for(int i = 1;i <= n;i++) s[i] = i; } int find_set(int x) { // 查找当前数字属于哪一个集合--s[i]表示集合类型，i 表示数字 return x == s[x] ? x : (find_set(s[x])); // 即 i 属于s[i]集合 } void union_set(int x,int y) { x = find_set(x); // 查找 x 所属的集合 y = find_set(y); // 查找 y 所属的集合 if(x != y) // 如果二者同属一个集合，不操作；反之，合并成一个集合 s[y] = s[x]; }
举例说明：元素1-5，有关系（1,2），（2,4）；
1.初始化结果：
| 表示集合--s[i] = | 1 | 2 | 3 | 4 | 5 |
| 表示元素-- i | 1 | 2 | 3 | 4 | 5 |
2.（1，2）合并
| 表示集合--s[i] = | 1 | 1 | 3 | 4 | 5 |
| 表示元素-- i | 1 | 2 | 3 | 4 | 5 |
3.(2,4)合并
| 表示集合--s[i] = | 1 | 1 | 3 | 2 | 5 |
| 表示元素-- i | 1 | 2 | 3 | 4 | 5 |
（此中表示为，元素 4 属于集合 2 中，而集合2又属于集合1，所以4的根结点为1，即1 = find_set(4)）
此时即有s[1] = s[2] = s[4] = 1(1号集合，包含1、2、4三个元素)，s[3] = 3(3号集合，一个元素) ，s[5] = 5(5号集合，一个元素) 共三个集合。
1213程序代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 1010; int s[maxn]; void inis_set(int n) { // 对数组进行初始化 for(int i = 1;i <= n;i++) s[i] = i; } int find_set(int x) { // 查找当前数字属于哪一个集合--s[i]表示集合类型，i 表示数字 return x == s[x] ? x : (find_set(s[x])); // 即 i 属于s[i]集合 } void union_set(int x,int y) { x = find_set(x); // 查找 x 所属的集合 y = find_set(y); // 查找 y 所属的集合 if(x != y) // 如果二者同属一个集合，不操作；反之，合并成一个集合 s[y] = s[x]; } int main() { int t; scanf("%d",&t); int n,m; int a,b; while(t--) { scanf("%d %d",&n,&m); inis_set(n); while(m--) { scanf("%d %d",&a,&b); union_set(a,b); } int ans = 0; for(int i = 1;i <= n;i++) if(s[i] == i) ans++; cout<<ans<<endl; } return 0; }
合并优化（从该元素搜索到其根结点的长度为树高（当做一棵树来看），把高度较小的集合并到较大的集合之上，能减少树的高度，使优化）；
查询优化（在查找x的根结点时，找到根结点后，逐一把途径结点所属的集合直接标记为s[x],这样，其元素i对应的集合s[i] = s[x]）;
优化代码：
int s[maxn]; int height[maxn]; void inis_set(int n) { // 对数组进行初始化 for(int i = 1;i <= n;i++) { s[i] = i; height[i] = 0; // 起始高度为 0 } } int find_set(int x) { // 查找当前数字属于哪一个集合 if(x != s[x]) s[x] = find_set(s[x]); // 途径所有的结点所属集合改为根结点 return s[x]; } void union_set(int x,int y) { // 合并优化 x = find_set(x); // 查找 x 所属的集合 y = find_set(y); // 查找 y 所属的集合 if(height[x] == height[y]) { height[x] = height[x] + 1; // 树高一样，即树高加一 s[y] = x; // 修改 s[y]集合的值（s[y] = s[x]） } else // 树高不一样，矮的接到高的树上 ，树高不变 if(height[x] > height[y]) s[y] = x; else s[x] = y; }
1213代码：（但是没过题，可能是set的原因吧，没想到是何原因，以后知道了来改吧）
#include <bits/stdc++.h> using namespace std; const int maxn = 1010; int s[maxn]; int height[maxn]; void inis_set(int n) { // 对数组进行初始化 for(int i = 1;i <= n;i++) { s[i] = i; height[i] = 0; // 起始高度为 0 } } int find_set(int x) { // 查找当前数字属于哪一个集合 if(x != s[x]) s[x] = find_set(s[x]); // 途径所有的结点所属集合改为根结点 return s[x]; } void union_set(int x,int y) { // 合并优化 x = find_set(x); // 查找 x 所属的集合 y = find_set(y); // 查找 y 所属的集合 if(height[x] == height[y]) { height[x] = height[x] + 1; // 树高一样，即树高加一 s[y] = x; // 修改 s[y]集合的值（s[y] = s[x]） } else // 树高不一样，矮的接到高的树上 ，树高不变 if(height[x] > height[y]) s[y] = x; else s[x] = y; } int main() { int t; scanf("%d",&t); int n,m; int a,b; set<int> st; while(t--) { scanf("%d %d",&n,&m); inis_set(n); while(m--) { scanf("%d %d",&a,&b); union_set(a,b); } for(int i = 1;i <= n;i++) st.insert(s[i]); cout<<st.size()<<endl; st.clear(); } return 0; }
2021-04-11
hdu--1213--Submit Your Solution--并查集
原文：https://www.cnblogs.com/2015-16/p/14645811.html
