1+ package src .main .java .com .dataStructures ;
2+
3+ import java .io .Serializable ;
4+ import java .util .*;
5+
6+ /**
7+ * An implementation of disjoint-set, represented by rooted trees.
8+ * <p>
9+ * Actually, the instance of {@link DisjointSet} is a disjoint-set forests.
10+ *
11+ * <p>
12+ * Disjoint-set operations:
13+ * <p>
14+ * 1. quickly unites two sets into a new set, requiring O(1) time.
15+ * <p>
16+ * 2. quickly query two elements whether contained in the same set, requiring about O(1) time.
17+ *
18+ * @author yangxf
19+ */
20+ public class DisjointSet <T >implements Serializable {
21+ private static final long serialVersionUID =3134700471905625636L ;
22+
23+ private Map <T ,Node <T >>nodeMap =new HashMap <>();
24+
25+ /**
26+ * Add an element to the disjoint-set forests as a set.
27+ */
28+ public void makeSet (T element ) {
29+ checkNotNull (element ,"element" );
30+ nodeMap .putIfAbsent (element ,new Node <>());
31+ }
32+
33+ /**
34+ * Unites the set that contains left and the set that contains right
35+ * into a new set with the union-by-rank heuristic.
36+ * <p>
37+ * Rank is an upper bound on the height of node.
38+ */
39+ public void union (T left ,T right ) {
40+ checkNotNull (left ,"element" );
41+ checkNotNull (right ,"element" );
42+
43+ Node <T >leftNode =nodeMap .get (left ),
44+ rightNode =nodeMap .get (right );
45+
46+ if (leftNode ==null ) {
47+ throw new NoSuchElementException (left .toString ());
48+ }
49+
50+ if (rightNode ==null ) {
51+ throw new NoSuchElementException (right .toString ());
52+ }
53+
54+ Node <T >leftSet =findSet (leftNode ),
55+ rightSet =findSet (rightNode );
56+
57+ if (leftSet ==rightSet ) {
58+ return ;
59+ }
60+
61+ if (leftSet .rank <rightSet .rank ) {
62+ leftSet .parent =rightSet ;
63+ }else {
64+ rightSet .parent =leftSet ;
65+ if (leftSet .rank ==rightSet .rank ) {
66+ leftSet .rank ++;
67+ }
68+ }
69+ }
70+
71+ /**
72+ * Query two elements whether contained in the same set.
73+ */
74+ public boolean isConnected (T left ,T right ) {
75+ if (left ==null ||right ==null ) {
76+ return false ;
77+ }
78+
79+ Node <T >leftNode =nodeMap .get (left );
80+ if (leftNode ==null ) {
81+ return false ;
82+ }
83+
84+ Node <T >rightNode =nodeMap .get (right );
85+ if (rightNode ==null ) {
86+ return false ;
87+ }
88+
89+ if (leftNode ==rightNode ) {
90+ return true ;
91+ }
92+
93+ return findSet (leftNode ) ==findSet (rightNode );
94+ }
95+
96+ public Collection <Set <T >>toSets () {
97+ Map <Node <T >,Set <T >>setMap =new HashMap <>();
98+ for (Map .Entry <T ,Node <T >>entry :nodeMap .entrySet ()) {
99+ setMap .computeIfAbsent (findSet (entry .getValue ()),k ->new HashSet <>())
100+ .add (entry .getKey ());
101+ }
102+ return setMap .values ();
103+ }
104+
105+ public void show () {
106+ toSets ().forEach (System .out ::println );
107+ }
108+
109+ /**
110+ * Find the set that contains the node, actual is the first node of the set.
111+ * <p>
112+ * Backtracking with path compression.
113+ */
114+ private Node <T >findSet (Node <T >node ) {
115+ if (node !=node .parent ) {
116+ node .parent =findSet (node .parent );
117+ }
118+ return node .parent ;
119+ }
120+
121+ private static void checkNotNull (Object obj ,String msg ) {
122+ if (obj ==null ) {
123+ throw new NullPointerException (msg +" must be not null" );
124+ }
125+ }
126+
127+ static class Node <T > {
128+ int rank ;
129+ Node <T >parent ;
130+
131+ Node () {
132+ parent =this ;
133+ }
134+ }
135+
136+ }