【算法】837.连通块中点的数量

题目

837. 连通块中点的数量

思路

与上一题类似，多了一个统计集合数量，可以定义一个数组用于记录集合个数，初始时设置为1，每要合并就更新一次。

代码 #include<iostream> using namespace std; const int N = 100010; int n, m; int p[N],siz[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; siz[i] = 1; } while (m--) { char op[3]; cin >> op; int a, b; if (op[0] == 'C') { cin >> a >> b; if (find(a) == find(b)) continue; siz[find(b)] = siz[find(a)] + siz[find(b)]; p[find(a)] = find(b); } else if (op[1] == '1') { cin >> a >> b; if (find(a) == find(b)) cout << "Yes" << endl; else cout << "No" << endl; } else { cin >>a; cout << siz[find(a)] << endl; } } return 0; }