并查集的作用
并查集是用树的形式维护所有集合
每一个集合用一个树来维护
每一个集合的编号是它根节点的编号
令每一个树根的p[x] = x
然后对于每一个点，都存储一下这个点的父节点是谁，p[x] = ?
然后当我们想求某个点属于哪个集合的时候
就找到这个点的father，然后看其是不是树根，不是的话就继续向上找。寻根问祖，追本溯源，找它祖宗
在问题2中，可以优化，用路径压缩
在x找到它的根节点时，把这条路径上所有点的父节点都直接指向根节点 ------路径压缩
并查集加了这一个优化之后，就可以看成是O(1)的时间复杂度了
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100010; 4 int p[N]; //存储每个元素父节点是谁 5 int find(int x) { //返回x的祖宗节点，即返回x所在集合的编号 ,加上路径压缩优化 6 if (p[x] != x) { 7 p[x] = find(p[x]); 8 } 9 return p[x]; 10 } 11 int main() { 12 int n, m; 13 cin >> n >> m; 14 for (int i = 1; i <= n; i++) { 15 p[i] = i; 16 } 17 while (m--) { 18 string op; 19 int a, b; 20 cin >> op; 21 if (op == "M") { 22 cin >> a >> b; 23 p[find(a)] = find(b); 24 } else { 25 cin >> a >> b; 26 if (find(a) == find(b)) { 27 cout << "Yes" << endl; 28 } else { 29 cout << "No" << endl; 30 } 31 } 32 } 33 return 0; 34 }
原文链接: https://www.cnblogs.com/fx1998/p/13291313.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/365930
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
