Disjoint Union Sets

It is a rainy Sunday morning in the Twin Cities of Minneapolis and St. Paul. Rain started last evening around 08:00 PM and according to the weather forecast will subside later tonight around 10:00 PM. Not a nice day to be outdoors or grilling.

Last Friday my son mentioned that he would be going shopping on Saturday morning to the Costco Minneapolis Business Center Warehouse. My wife and I decided to join him at 07:00 AM (opening time). We met in the parking lot, donned our gloves and mask, and headed in. We have been at the Restaurant Depot many times, but were nicely surprised with the size of the Costco facility and the variety of items. From now on my wife and I will make the trip from home (30 minutes about 20 miles away) a couple times a month to the Costco in Minneapolis. We believe it is worth the drive.

My wife and I cook and bake. I like to bake deserts, breads and Italian cuisine. My wife cooks lunch during the workdays. We both cook on weekends. We have breakfast which I prepare every day and we both skip dinner. The point that I am trying to make is that we did not start cooking or baking due to the coronavirus pandemic.

Last week we noticed that we were running very low on yeast. We went grocery shopping last Tuesday morning and where not able to find yeast at Costco in Eagan, MN or Trader Joe’s in St. Paul. Back home, I went to Amazon.com and ordered a 2 pound pouch of Red Star dry yeast. The total after taxes (we do have Amazon Prime) came to $24.99 USD. I thought it was expensive but it seems that every one and their brother are baking now a day. The delivery will be sometime tomorrow (Monday).

While at Costco we found lots of Red Star dry yeast in the same 2 lb pouches we ordered from Amazon. That is the same yeast we have been using for over a decade. What we found disgusting was that Costco had the same 2 lb pouches of yeast for under $4.50 USD each. We bought two pouches (totaling 4 lbs) for about $9.00 USD. They should last a year or so.

Back at home, I went down to my office with the idea of cancelling the order. I was not able. It seems that you can cancel without an issue if the order has not been submitted to the seller. It had already been submitted so I could not cancel it. I thought I could return the unopened package. No luck there either. Since the package contains yeast which can be consumed by humans, Amazon does not allow such type of items to be returned. As I am typing this text, I got a notification that the yeast from Amazon has been delivered. I will go up and check… Not there. It must have been delivered to our mailbox. I will check later today when the rain is lighter.

I will never again order from Amazon items that are priced 555% higher without first checking availability for the items in multiple stores in the Twin Cities area!!!

The main subject of this post is to experiment with Disjoint Sets. It happens that if you have a set of items, you can specify a relation and then check if an item belongs to some set and collect some information from the sets.

Microsoft Windows [Version 10.0.18363.836]
(c) 2019 Microsoft Corporation. All rights reserved.

# **** ****
C:\Users\johnc>dir
05/13/2020  03:12 PM    <DIR>          .
05/13/2020  03:12 PM    <DIR>          ..
05/13/2020  03:07 PM                57 .angular-config.json
05/13/2020  03:03 PM    <DIR>          .config
09/22/2019  08:00 AM    <DIR>          .eclipse
03/15/2020  08:38 AM                59 .gitconfig
04/23/2020  11:11 AM    <DIR>          .p2
05/07/2020  08:11 AM         1,005,502 .pipwin
04/21/2020  08:07 AM    <DIR>          .pylint.d
09/22/2019  08:00 AM    <DIR>          .tooling
03/10/2020  03:53 PM    <DIR>          .vscode
05/13/2020  07:59 AM    <DIR>          3D Objects
05/13/2020  07:59 AM    <DIR>          Contacts
04/08/2020  07:59 AM    <DIR>          ContainsCloseNums
02/17/2020  03:52 PM    <DIR>          Documents
05/13/2020  02:55 PM    <DIR>          Downloads
09/22/2019  07:57 AM    <DIR>          eclipse
09/22/2019  07:59 AM    <DIR>          eclipse-workspace_0
05/13/2020  07:59 AM    <DIR>          Favorites
05/13/2020  07:59 AM    <DIR>          Links
05/13/2020  07:59 AM    <DIR>          Music
05/13/2020  03:49 PM    <DIR>          my-app
09/12/2019  04:36 PM    <DIR>          NCH Software Suite
05/17/2020  07:41 AM    <DIR>          OneDrive
05/04/2020  03:42 PM    <DIR>          pipwin
05/13/2020  07:59 AM    <DIR>          Saved Games
05/13/2020  07:59 AM    <DIR>          Searches
05/11/2020  03:04 PM    <DIR>          source
05/13/2020  07:59 AM    <DIR>          Videos
05/05/2020  01:30 PM    <DIR>          vimfiles
05/11/2020  12:13 PM    <DIR>          workspace0
05/05/2020  01:51 PM             3,281 _viminfo

# **** ****
C:\Users\johnc>cd workspace0

# **** ****
C:\Users\johnc\workspace0>dir
05/11/2020  12:13 PM    <DIR>          .
05/11/2020  12:13 PM    <DIR>          ..
04/01/2020  08:57 AM    <DIR>          BST-Search
04/27/2020  08:46 AM    <DIR>          ClassesInPython
05/11/2020  03:07 PM    <DIR>          ComponentsInAGraph
04/10/2020  11:34 AM    <DIR>          ComposeRanges
04/08/2020  08:04 AM    <DIR>          ContainsCloseNums
05/08/2020  12:01 PM    <DIR>          CS50Python
05/07/2020  02:44 PM    <DIR>          DownToZeroII
04/05/2020  08:32 AM    <DIR>          GraphBFS
04/21/2020  07:46 AM    <DIR>          Knights
04/24/2020  08:33 AM    <DIR>          Minesweeper
04/17/2020  03:41 PM    <DIR>          MissingNumber
03/29/2020  08:30 AM    <DIR>          ORCost
04/23/2020  11:13 AM    <DIR>          Python-Tutorial-CS50
04/22/2020  04:37 PM    <DIR>          PythonTutorial
04/19/2020  07:46 AM    <DIR>          RobotInAGrid
03/10/2020  04:24 PM    <DIR>          SortOnFrequency
04/29/2020  02:47 PM    <DIR>          UsingWithPython
04/28/2020  02:52 PM    <DIR>          WorkingWithFiles

# **** ****
C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/DisjointSet.git
Cloning into 'DisjointSet'...
remote: Enumerating objects: 3, done.
remote: Counting objects: 100% (3/3), done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (3/3), 814 bytes | 8.00 KiB/s, done.

# **** ****
C:\Users\johnc\workspace0>dir
05/17/2020  08:05 AM    <DIR>          .
05/17/2020  08:05 AM    <DIR>          ..
04/01/2020  08:57 AM    <DIR>          BST-Search
04/27/2020  08:46 AM    <DIR>          ClassesInPython
05/11/2020  03:07 PM    <DIR>          ComponentsInAGraph
04/10/2020  11:34 AM    <DIR>          ComposeRanges
04/08/2020  08:04 AM    <DIR>          ContainsCloseNums
05/08/2020  12:01 PM    <DIR>          CS50Python
05/17/2020  08:05 AM    <DIR>          DisjointSet
05/07/2020  02:44 PM    <DIR>          DownToZeroII
04/05/2020  08:32 AM    <DIR>          GraphBFS
04/21/2020  07:46 AM    <DIR>          Knights
04/24/2020  08:33 AM    <DIR>          Minesweeper
04/17/2020  03:41 PM    <DIR>          MissingNumber
03/29/2020  08:30 AM    <DIR>          ORCost
04/23/2020  11:13 AM    <DIR>          Python-Tutorial-CS50
04/22/2020  04:37 PM    <DIR>          PythonTutorial
04/19/2020  07:46 AM    <DIR>          RobotInAGrid
03/10/2020  04:24 PM    <DIR>          SortOnFrequency
04/29/2020  02:47 PM    <DIR>          UsingWithPython
04/28/2020  02:52 PM    <DIR>          WorkingWithFiles

# **** ****
C:\Users\johnc\workspace0>cd DisjointSet

# **** ****
C:\Users\johnc\workspace0\DisjointSet>dir
05/17/2020  08:05 AM    <DIR>          .
05/17/2020  08:05 AM    <DIR>          ..
05/17/2020  08:05 AM               357 README.md

# **** ****
C:\Users\johnc\workspace0\DisjointSet>type README.md
# DisjointSet
Experimenting with disjoint sets using Java 8.

Finding out which data structures work best.
Experiemnting with functions / methods in order to determine the smallest set.

To read more about this code please follow the following link to a post in my blog:

T.B.D.

Hope you enjoy and have as much fun as I did.

Regards;

John

I went to GitHub and created a repository for this project. Once created I clone I started work on some code.

5
0 2
4 2
3 1

4 0
1 0

main <<< n: 5
main <<< dus:
     n: 5
  rank: [0, 0, 0, 0, 0]
parent: [0, 1, 2, 3, 4]

main <<< x: 0 y: 2
union <<< xRoot: 0 yRoot: 2
union <<< rank[0]: 0
union <<< rank[2]: 0

main <<< x: 4 y: 2
union <<< xRoot: 4 yRoot: 0
union <<< rank[4]: 0
union <<< rank[0]: 1

main <<< x: 3 y: 1
union <<< xRoot: 3 yRoot: 1
union <<< rank[3]: 0
union <<< rank[1]: 0

main <<< dus:
     n: 5
  rank: [1, 0, 0, 1, 0]
parent: [0, 3, 0, 3, 0]

main <<< x: 4 y: 0
x: 4 and y: 0 friends

main <<< x: 1 y: 0
x: 1 and y: 0 NOT friends

In the screen capture we start by providing data to the disjoint set. Once the set is updated we check some relations.

The first line contains the number of nodes. In our case we will have five. The nodes will be in the following set {0, 1, 2, 3, 4}.

The following three lines ending with a blank one contain relationships. Let’s assume the nodes represent people and the relationships represent friendships. The line containing 0 2 represents a friendship between nodes zero and two. The next line 4 2 represents a friendship between nodes four and two. The last line before the blank one containing 3 1 represents a friendship relationship between nodes three and one.

We can visualize the relationships as follows:

R0:  0 <-> 2 <-> 4

R1:  1 <-> 3

The next line represents a query to find out if there is a relationship between nodes four and zero. The answer would be yes because 0, 2 and 4 are in the same set. The last line queries if nodes one and zero have a friendship. Since node one is in a different set than node zero, the answer would be no.

The program displays the number of nodes followed by a representation of the data that we will use to represent disjoint sets. We use the number of nodes and two arrays each of size n.

After the data has been initialized, we process the three relations. We will be updating the two arrays. After the relationships are defined, we display the data in our object. More on this will follow.

We then check if 4 and 0 are friends (belong to the same set). As expected the answer is yes. The following query using 1 and 0 comes back indicating they are not friends (do not belong to the same set).

In the Disjoint-set data structure, in the Representation section the following sentence contains a definition that is important to keep in mind.

“However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.”

The rank array tells us that 0 and 3 are roots (representatives). This is encoded based on the fact that the rank array holds a 1.

In the parent array, we start with position 0 which is a representative. The other entries with value 0 are in the same set; in this case 0, 2, and 4 are friends. If we start with position 1 holding a 3, we find position 3 which also contains a 3 indicating that 1 and 3 are in the same set (are friends).

The last four lines represent the queries and the respective results. 4 and 0 are in the same set so they are friends; while 1 and 0 are in different sets so they are not friends.

10
0 1
1 3
2 5
2 8
9 4
6 9

9 1
1 3
1 5
5 8
4 6
6 9
1 2
5 6
7 8

main <<< n: 10
main <<< dus:
     n: 10
  rank: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
parent: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

main <<< x: 0 y: 1
union <<< xRoot: 0 yRoot: 1
union <<< rank[0]: 0
union <<< rank[1]: 0

main <<< x: 1 y: 3
union <<< xRoot: 0 yRoot: 3
union <<< rank[0]: 1
union <<< rank[3]: 0

main <<< x: 2 y: 5
union <<< xRoot: 2 yRoot: 5
union <<< rank[2]: 0
union <<< rank[5]: 0

main <<< x: 2 y: 8
union <<< xRoot: 2 yRoot: 8
union <<< rank[2]: 1
union <<< rank[8]: 0

main <<< x: 9 y: 4
union <<< xRoot: 9 yRoot: 4
union <<< rank[9]: 0
union <<< rank[4]: 0

main <<< x: 6 y: 9
union <<< xRoot: 6 yRoot: 9
union <<< rank[6]: 0
union <<< rank[9]: 1

main <<< dus:
     n: 10
  rank: [1, 0, 1, 0, 0, 0, 0, 0, 0, 1]
parent: [0, 0, 2, 0, 9, 2, 9, 7, 2, 9]

main <<< x: 9 y: 1
x: 9 and y: 1 NOT friends

main <<< x: 1 y: 3
x: 1 and y: 3 friends

main <<< x: 1 y: 5
x: 1 and y: 5 NOT friends

main <<< x: 5 y: 8
x: 5 and y: 8 friends

main <<< x: 4 y: 6
x: 4 and y: 6 friends

main <<< x: 6 y: 9
x: 6 and y: 9 friends

main <<< x: 1 y: 2
x: 1 and y: 2 NOT friends

main <<< x: 5 y: 6
x: 5 and y: 6 NOT friends

main <<< x: 7 y: 8
x: 7 and y: 8 NOT friends

In this example we are getting 10 numbers which will be in the set { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. The next set of lines indicates that the following sets are being defined:

R0:  0 <-> 1 <-> 3

R1:  2 <-> 5 <-> 8

R3:  4 <-> 6 <-> 9

R4:  7

Based on these sets we ask a set of queries. You can look at the results and verify that the queries are answered as expected.

10
0 1
1 2
3 4
6 7
7 8
8 9

1 2
3 4
5 6
7 8

main <<< n: 10
main <<< dus:
     n: 10
  rank: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
parent: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

main <<< x: 0 y: 1
union <<< xRoot: 0 yRoot: 1
union <<< rank[0]: 0
union <<< rank[1]: 0

main <<< x: 1 y: 2
union <<< xRoot: 0 yRoot: 2
union <<< rank[0]: 1
union <<< rank[2]: 0

main <<< x: 3 y: 4
union <<< xRoot: 3 yRoot: 4
union <<< rank[3]: 0
union <<< rank[4]: 0

main <<< x: 6 y: 7
union <<< xRoot: 6 yRoot: 7
union <<< rank[6]: 0
union <<< rank[7]: 0

main <<< x: 7 y: 8
union <<< xRoot: 6 yRoot: 8
union <<< rank[6]: 1
union <<< rank[8]: 0

main <<< x: 8 y: 9
union <<< xRoot: 6 yRoot: 9
union <<< rank[6]: 1
union <<< rank[9]: 0

main <<< dus:
     n: 10
  rank: [1, 0, 0, 1, 0, 0, 1, 0, 0, 0]
parent: [0, 0, 0, 3, 3, 5, 6, 6, 6, 6]

main <<< x: 1 y: 2
x: 1 and y: 2 friends

main <<< x: 3 y: 4
x: 3 and y: 4 friends

main <<< x: 5 y: 6
x: 5 and y: 6 NOT friends

main <<< x: 7 y: 8
x: 7 and y: 8 friends

We have 10 elements in the set. The relationships are grouped as follows:

R0:  0 <-> 1 <-> 2

R1:  3 <-> 4

R2:  6 <-> 7 <-> 8 <-> 9

R3:  5

The next four queries come back with the correct results. Please take a look at the rank array. The entries with value 1 hold representatives for the sets. In this case { 0, 3, 6 }. Note that parent[5] is not a representative and there are no other entries in parent array holding a 5. This implies this entry does not belong to a set with multiple values. The entries 3 and 4 in the parents array hold the same value 3 so 3 and 4 are in the same set. Finally, entries in array parent 0, 1, and 2 are in the same set with representative 0.

10
0 2
2 4
4 6
6 8
1 3
3 5
5 7
7 9

0 1
1 2
2 3
3 4
4 5

main <<< n: 10
main <<< dus:
     n: 10
  rank: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
parent: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

main <<< x: 0 y: 2
union <<< xRoot: 0 yRoot: 2
union <<< rank[0]: 0
union <<< rank[2]: 0

main <<< x: 2 y: 4
union <<< xRoot: 0 yRoot: 4
union <<< rank[0]: 1
union <<< rank[4]: 0

main <<< x: 4 y: 6
union <<< xRoot: 0 yRoot: 6
union <<< rank[0]: 1
union <<< rank[6]: 0

main <<< x: 6 y: 8
union <<< xRoot: 0 yRoot: 8
union <<< rank[0]: 1
union <<< rank[8]: 0

main <<< x: 1 y: 3
union <<< xRoot: 1 yRoot: 3
union <<< rank[1]: 0
union <<< rank[3]: 0

main <<< x: 3 y: 5
union <<< xRoot: 1 yRoot: 5
union <<< rank[1]: 1
union <<< rank[5]: 0

main <<< x: 5 y: 7
union <<< xRoot: 1 yRoot: 7
union <<< rank[1]: 1
union <<< rank[7]: 0

main <<< x: 7 y: 9
union <<< xRoot: 1 yRoot: 9
union <<< rank[1]: 1
union <<< rank[9]: 0

main <<< dus:
     n: 10
  rank: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
parent: [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

main <<< x: 0 y: 1
x: 0 and y: 1 NOT friends

main <<< x: 1 y: 2
x: 1 and y: 2 NOT friends

main <<< x: 2 y: 3
x: 2 and y: 3 NOT friends

main <<< x: 3 y: 4
x: 3 and y: 4 NOT friends

main <<< x: 4 y: 5
x: 4 and y: 5 NOT friends

One more example and will look at the code.

This example also holds ten values. Perhaps I should have used examples all with different counts. The sets represented are:

R0:  0 <-> 2 <-> 4 <-> 6 <-> 8

R1:  1 <-> 3 <-> 5 <-> 7 <-> 9

It seems like all even numbers (including 0) are in the first set, while the odd numbers are in the second set. All numbers have been accounted for in one of the two sets.

Let’s take a look at the rank array. It makes sense that we only have two representatives, 0 and 1 for the even and odd sets.

The parent array shows that entries 0, 2, 4, 6, and 8 share a common representative in 0 (even set) while entries 1, 3, 5, 7, and 9 have representative in 1 (odd set). Hopefully the way the two arrays work is understood.

As expected all the queries fail because they contain an odd and an even number.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read the number of elements ****
        int n = Integer.parseInt(sc.nextLine());

        // ??? ?????
        System.out.println("main <<< n: " + n);

        // **** instantiate the class ****
        DisjointUnionSets dus = new DisjointUnionSets(n);

        // ???? ????
        System.out.println("main <<< dus: " + dus.toString() + "\n");

        // **** loop reading friendships (list MUST end with empty line) ****
        String s;
        do {

            // **** read the next relationship ****
            s = sc.nextLine();

            // **** remove leading and trailing blanks characters ****
            s = s.trim();

            // **** process union (if present) ****
            if (!s.isEmpty()) {

                // **** extract x and y ****
                String[] ss = s.split(" ");
                int x = Integer.parseInt(ss[0]);
                int y = Integer.parseInt(ss[1]);

                // ???? ????
                System.out.println("main <<< x: " + x + " y: " + y);

                // **** ****
                dus.union(x, y);

                // ???? ????
                System.out.println();
            }
        } while(!s.isEmpty());

        // ???? ????
        System.out.println("main <<< dus: " + dus.toString() + "\n");

        // **** loop reading and checking relationships (list MUST end with empty line) ****
        do {

            // **** read the next relationship ****
            s = sc.nextLine();

            // **** remove leading and trailing blanks characters ****
            s = s.trim();

            // **** process union (if present) ****
            if (!s.isEmpty()) {

              // **** extract x and y ****
              String[] ss = s.split(" ");
              int x = Integer.parseInt(ss[0]);
              int y = Integer.parseInt(ss[1]);

              // ???? ????
              System.out.println("main <<< x: " + x + " y: " + y);

              // **** check if x and y are friends ****
              if (dus.find(x) == dus.find(y)) {
                  System.out.println("x: " + x + " and y: " + y + " friends");
              } else {
                  System.out.println("x: " + x + " and y: " + y + " NOT friends");
              }

              // ???? ????
              System.out.println();
            }

        } while (!s.isEmpty());

        // **** close scanner ****
        sc.close();
    }

The test scaffolding matches what we have seen in the previous examples.

It starts by opening a scanner and reading the number of elements in the set. We create an object of type DisjointUnionSets.

We then enter a loop. We read a line and if needed perform a union of the two values. In production we should check that the values are in the specified range 0 to n – 1. We then put them in the same set using the union method.

We skip the blank line.

We now loop processing queries about the values. We read a line and extract the values. Once again, in production we should check the range. This time we check if both values have the same representative. If they do they belong to the same set (are friends) or they do not (not friends).

When all is wet and done we close the scanner.

    // **** class members ****
    int[] rank;
    int[] parent;
    int n;

This Java code snippet shows the three members of the class. We have been discussing how they are used in the examples so at this point I do not have much to add.

    /**
     * Constructor.
     */
    public DisjointUnionSets(int n) {

        // **** ****
        this.rank = new int[n];
        this.parent = new int[n];
        this.n = n;

        // **** make the set ****
        makeSet();
    }

The constructor allocates the two arrays and sets the value of n. It then calls a private method to initialize the parent array.

   /**
     * Create n sets with a sungle item in each.
     */
    private void makeSet() {

        // **** all elements are in their own set ****
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

The method sets the values in the parent array with the value associate with its order. This indicates that each value represents a disjoint set. We have seen in previous examples that when all the relationships were processed we had a set with a single node. In practice we could have multiple values in their original sets (no friends).

   /**
     * Returns representative of x's set 
     */
    int find(int x) { 

        // **** ****
        if (parent[x] != x) { 
            parent[x] = find(parent[x]); 
        } 

        // **** ****
        return parent[x]; 
    } 

This is a recursive method. It finds the representative for the specified value. As we discussed, if both values have the same representative they are in the same set; otherwise they are not in the same set so they are not friends.

   /**
     * Unites the set that includes x and the set that includes x 
    */
    void union(int x, int y) {

        // **** find representatives of the two sets ****
        int xRoot = find(x);
        int yRoot = find(y); 

        // ???? ????
        System.out.println("union <<< xRoot: " + xRoot + " yRoot: " + yRoot);

        // **** if elements in the same set; nothing else to do ****
        if (xRoot == yRoot) 
            return; 
  
        // ???? ????
        System.out.println("union <<< rank[" + xRoot + "]: " + rank[xRoot]);
        System.out.println("union <<< rank[" + yRoot + "]: " + rank[yRoot]);

        // **** if x's rank is less than y's rank ****
        if (rank[xRoot] < rank[yRoot]) // **** move x under y so that depth of tree remains less parent[xRoot] = yRoot; // **** if x's rank is greater than y's rank **** else if (rank[xRoot] > rank[yRoot]) 
  
            // **** move y under x so that depth of tree remains less ****
            parent[yRoot] = xRoot; 
        
        // **** if ranks are the same ****
        else { 

            // **** move y under x (doesn't matter which one goes where) ****
            parent[yRoot] = xRoot; 
  
            // **** increment the result tree's rank by 1 ****
            rank[xRoot] = rank[xRoot] + 1; 
        } 
    } 

The union method puts the two values in the same set.

We start by finding the representatives for both values. If the values match, then they are in the same set and we are done.

We then check if the rank array. There are three possibilities with the values. In the first two conditions we move the ranks in order to have the one with less value to the left. If the rank values are the same, the order does not matter, we just need to increment the ranks by one to indicate these values have a different representative.

    /**
     * Return a string representation of the object.
     */
    public String toString() {

        // **** ****
        StringBuilder sb = new StringBuilder();

        sb.append("\n     n: " + this.n);
        sb.append("\n  rank: " + Arrays.toString(this.rank));
        sb.append("\nparent: " + Arrays.toString(this.parent));

        // **** ****
        return sb.toString();
    }

This is used to display the object. There was no need to use a StringBuilder given the small number of fields. For efficiency I prefer to use a StringBuilder over string concatenations.

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git status
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        DisjointUnionSets.java

nothing added to commit but untracked files present (use "git add" to track)

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git add DisjointUnionSets.java

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
  (use "git restore --staged <file>..." to unstage)
        new file:   DisjointUnionSets.java

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git commit -m "initial commit includes test scaffolding"
[master 81e9ab8] initial commit includes test scaffolding
 1 file changed, 206 insertions(+)
 create mode 100644 DisjointUnionSets.java

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.61 KiB | 1.61 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/DisjointSet.git
   9f5e1a2..81e9ab8  master -> master

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git status
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\DisjointSet>git log
commit 81e9ab83b7785431edc1f6563ad379a245315525 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Sun May 17 11:17:43 2020 -0500

    initial commit includes test scaffolding

commit 9f5e1a26b1bc303637d35cc2fb609d9becd3901d
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date:   Sun May 17 08:04:32 2020 -0500

    Create README.md

Now that we are done we need to get our code to our GitHub repository. If you follow my blog, the steps are quite predictable. Note that I like to get status after most commands just to make sure all is well as I proceed.

I will use the knowledge regarding disjoint sets in this post to solve a problem in the next post.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 967 subscribers to my blog!!!

Keep safe during the COVID-19 pandemic.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.