主要分为两步,find查找 和 union合并
    其中在find的过程中可以进行路径的压缩,在union的过程中可以利用size数组统计当前树的节点数,从而实现把节点数少的树合并到节点数多的树

    1. // 初始化
    2. vector<int> father(size);
    3. void build(int size)
    4. {
    5. for (int i = 0; i < size; ++i)
    6. {
    7. father[i] = i; // 初始化时所有节点的父节点都是自身
    8. }
    9. }
    10. // 查找
    11. int find(int x)
    12. {
    13. if (father[x] != x)
    14. {
    15. father[x] = find(father[x]); // 此处起到了路径压缩的作用
    16. }
    17. return father[x];
    18. }
    19. // 合并
    20. vector<int> size(size, 1); // 用以记录树的节点数
    21. void union(int x, int y)
    22. {
    23. int father_x = find(x);
    24. int father_y = find(y);
    25. if (father_x == father_y) return;
    26. if (size[father_x] > size[father_y])
    27. {
    28. father[father_y] = father_x; // 让节点数少的链接到节点数多的
    29. size[father_x] += size[father_y];
    30. }
    31. else
    32. {
    33. father[father_x] = father_y;
    34. size[father_y] += size[father_x];
    35. }
    36. }