用并查集维护每个集合中的元素个数
还是用集合来维护连通块
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100010; 4 int p[N]; //存储每个元素父节点是谁 5 int se[N]; //记录每一个集合中点的数量 6 //规定只有根节点的size才有意义 7 int find(int x) { //返回x的祖宗节点,即返回x所在集合的编号 ,加上路径压缩优化 8 if (p[x] != x) { 9 p[x] = find(p[x]); 10 } 11 return p[x]; 12 } 13 int main() { 14 int n, m; 15 cin >> n >> m; 16 for (int i = 1; i <= n; i++) { 17 p[i] = i; 18 se[i] = 1; //开始时每个连通块中点的数量为1 19 } 20 while (m--) { 21 string op; 22 int a, b; 23 cin >> op; 24 if (op == "C") { 25 cin >> a >> b; 26 if (find(a) == find(b)) { //特判 27 continue; 28 } 29 se[find(b)] += se[find(a)]; 30 p[find(a)] = find(b); 31 } else if (op == "Q1"){ 32 cin >> a >> b; 33 if (find(a) == find(b)) { 34 cout << "Yes" << endl; 35 } else { 36 cout << "No" << endl; 37 } 38 } else { 39 cin >> a; 40 cout << se[find(a)] << endl; 41 } 42 } 43 return 0; 44 }
原文链接: https://www.cnblogs.com/fx1998/p/13298557.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/365913
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!