JAVA:实现Disjoint Sets不相交集合算法(附完整源码)

package com.thealgorithms.datastructures.disjointsets;

public class DisjointSets<T> {

    public Node<T> MakeSet(T x) {
        return new Node<T>(x);
    }

    ;

    public Node<T> FindSet(Node<T> node) {
        if (node != node.parent) {
            node.parent = FindSet(node.parent);
        }

        return node.parent;
    }

    public void UnionSet(Node<T> x, Node<T> y) {
        Node<T> nx = FindSet(x);
        Node<T> ny = FindSet(y);

        if (nx == ny) {
            return;
        }
        if (nx.rank > ny.rank) {
            ny.parent = nx;
        } else if (ny.rank > nx.rank) {
            nx.parent = ny;
        } else {
            nx.parent = ny;
            ny.rank++;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36