> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/disjoint-sets/implementation.md).

# 6.2. Implementation

This sections discusses the implementation of disjoint sets.

Let us create the [`DisjointSet`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/set/DisjointSet.java) class:

```java
public class DisjointSet {
    private final int[] subsets;

    public DisjointSet(int size) {
        subsets = new int[size];
        Arrays.fill(subsets, -1);
    }

    public DisjointSet(DisjointSet set) {
        subsets = Arrays.copyOf(set.subsets, set.subsets.length);
    }
}
```

* `L2`: the size of subset (`-1` implies `1` ID, `-2` implies `2` IDs, and so on).
* `L5-6`: every set is initialized with the size of `1`.
* `L9`: a copy constructor.

Let us define the `find()` method:

{% tabs %}
{% tab title="Baseline" %}

```java
public int find(int id) {
    return (subsets[id] < 0) ? id : find(subsets[id]);
}
```

{% endtab %}

{% tab title="Efficient" %}

```java
public int find(int id) {
    return (subsets[id] < 0) ? id : (subsets[id] = find(subsets[id]));
}
```

{% endtab %}
{% endtabs %}

* `L2`: returns the ID of the subset where the specific key belongs to.&#x20;

> What is the worst-case complexity of the `find()` method?

We then define the `inSameSet()` method:

```java
public boolean inSameSet(int key1, int key2) {
    return find(key1) == find(key2);
}
```

* `L2`: returns true if the two specific keys are in the same set.

Finally, let us define the `union()` method:

```java
public int union(int key1, int key2) {
    int r1 = find(key1);
    int r2 = find(key2);
    if (r1 == r2) return r1;

    if (subsets[r1] < subsets[r2]) {
        subsets[r1] += subsets[r2];
        subsets[r2] = r1;
        return r1;
    }
    else {
        subsets[r2] += subsets[r1];
        subsets[r1] = r2;
        return r2;
    }
}
```

* `L2-4`: return the subset ID where both `key1` and `key2` belongs to.
* `L6-10`: merges the set containing `key2` to the set containing `key1`.
* `L11-15`: merges the set containing `key1` to the set containing `key2`.