并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSetsDisjointSets）的合并及查询问题。常常在使用中以森林来表示。
#include <iostream> using namespace std; const int N = 100010; int p[N]; int find(int x)//返回祖宗结点 { if (p[x] != x) p[x] = find(p[x]);//硬使p[x]=它的祖宗结点 return p[x]; } int main() { int n, m; cin>>n>>m; for (int i = 1; i <= n; i ++ ) p[i] = i;//i是p[i]的父结点 while (m -- ) { char op; int a, b; cin>>op>>a>>b; if (op == 'M') p[find(a)] = find(b);//find[a]:a的祖宗结点find[b]:b的祖宗结点 else //也可以是op[0] //让a的祖宗结点的父节点指向b的祖宗结点 { //就是把a，b合并 if (find(a) == find(b)) puts("Yes");//如果a，b的祖宗结点一样，证明a，b在一个集合中 else puts("No"); } } return 0; }
p[find(a)] = find(b)解释
#include <iostream> using namespace std; const int N = 100010; int n, m; int p[N], cnt[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) { p[i] = i; cnt[i] = 1; } while (m -- ) { string op; int a, b; cin >> op; if (op == "C") { cin >> a >> b; a = find(a), b = find(b); if (a != b) { p[a] = b; cnt[b] += cnt[a]; } } else if (op == "Q1") { cin >> a >> b; if (find(a) == find(b)) puts("Yes"); else puts("No"); } else { cin >> a; cout << cnt[find(a)] << endl; } } return 0; }
🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈🏳️🌈
我们只需要遍历一下点的集合，如果两个点的横坐标或者众坐标相等，那么我们就把这两个点放入一个集合中
最后我们只需要统计一下有几个集合就知道解了，解的个数就是集合的个数减一，我们可以这么想如果有两个不相交的集合，我们只需要加一个点就可以让两个集合联系起来
#include <iostream> using namespace std; const int N= 1e5 + 10; struct node { int xi, yi; } w[N]; int p[N]; int find(int x) //路径压缩 { if (p[x]!=x) p[x]=find(p[x]); return p[x]; } void merge(int x, int y) { int a = find(x); int b = find(y); if (a != b) p[a] = b; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) p[i] = i;//初始化 for (int i = 1; i <= n; i++) scanf("%d%d", &w[i].xi, &w[i].yi); for (int i = 1; i < n; i++) //防止越界，i要小于n不能等 { for (int j = i + 1; j <= n; j++) { if (w[i].xi == w[j].xi || w[i].yi == w[j].yi)//横坐标相等||纵坐标相等 merge(i, j);//合并为一个联通块 //注意：这里合并的是i,j 不是w[i]w[j] //因为w[i]w[j]仅仅是判断横坐标纵坐标是否相等 //⭐⭐⭐i,j来组成联通块⭐⭐⭐ //if(find(i)!=find(j)) //p[find(i)]=find(j); } } //分散的点连成联通块后，判断有多少个联通块 int ans = 0; for (int i = 1; i <= n; ++i) if (p[i] == i) ans++; printf("%d\n", ans - 1); }
Code over！
