【刷题】数据结构——并查集：连通块中点的数量【记录集合元素个数】

利用并查集维护连通块。
只需在合并之前，如x并到y上，将x的数量加到y的数量上即可。

1、cnt[find(y)] += cnt[find(x)]
2、p[find(x)] = find(y)

#include using namespace std;const int N = 100005;int n, m;int p[N], idx, cnt[N];int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}int main() { scanf("%d%d", &n, &m); char op[3]; int x, y; for (int i = 1; i <= n; i ++ ) p[i] = i, cnt[i] = 1; while(m -- ) { scanf("%s", op); if (op[0] == 'C') { scanf("%d%d", &x, &y); if (find(x) == find(y)) continue; // 防止自己连自己导致元素翻倍 cnt[find(y)] += cnt[find(x)]; p[find(x)] = find(y); } else if (op[0] == 'Q' && op[1] == '1') { scanf("%d%d", &x, &y); if (find(x) == find(y)) printf("Yesn"); else printf("Non"); } else { scanf("%d", &x); printf("%dn", cnt[find(x)]); } } return 0;}