C - How Many Tables——并查集

淡淡的烟草味﹌ 2022-06-12 11:38 217阅读 0赞

Think:
1知识点:并查集
2反思:并查集初始化操作应注意已知n进而进行初始化

vjudge题目链接

以下为Accepted代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 1e3 + 4;
  6. int n, m, f[N];
  7. void Init();
  8. int get_f(int x);
  9. void Merge(int u, int v);
  10. int main(){
  11. int T, i, u, v, ans;
  12. scanf("%d", &T);
  13. while(T--){
  14. scanf("%d %d", &n, &m);
  15. ans = 0;
  16. Init();
  17. while(m--){
  18. scanf("%d %d", &u, &v);
  19. Merge(u, v);
  20. }
  21. for(i = 1; i <= n; i++){
  22. if(f[i] == i)
  23. ans++;
  24. }
  25. printf("%d\n", ans);
  26. }
  27. return 0;
  28. }
  29. void Init(){
  30. for(int i = 1; i <= n; i++)
  31. f[i] = i;
  32. }
  33. void Merge(int u, int v){
  34. int t1 = get_f(u);
  35. int t2 = get_f(v);
  36. f[t2] = t1;
  37. }
  38. int get_f(int x){
  39. if(f[x] == x)
  40. return f[x];
  41. else {
  42. f[x] = get_f(f[x]);
  43. return f[x];
  44. }
  45. }

发表评论

表情:
评论列表 (有 0 条评论,217人围观)

还没有评论,来说两句吧...

相关阅读