HelloKoding

Practical coding guides

Disjoint-set Data Structure

In this article, you will learn about Disjoint-set data structure and its implementation

Disjoint-sets are sets whose intersection is the empty set. For example, {0, 1, 2} and {3} are disjoint sets, while {0, 1, 2} and {2, 3} are not.

Problem

  • Given some separated elements grouped in disjoint sets
  • Find whether 2 elements in the same set or not

Analysis

  • How to determine if 2 elements are in the same set?

    Check if they have the same root/representative.

  • How to determine the root/representative of a set?

    Unionizing 2 elements by a bigger index or by a higher rank

Approach 1: Union by bigger index

Find with compress path and Union by bigger index

DisjoinSetUnionByBiggestIndex.java

package com.hellokoding.datastructure;

public class DisjoinSetUnionByBiggestIndex {
    int[] parents;
    int N;

    DisjoinSetUnionByBiggestIndex(int N) {
        this.N = N;
        parents = new int[N];
        initDisjoinSet();
    }

    void initDisjoinSet() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    int findRoot(int x) {
        if (parents[x] != x) {
            parents[x] = findRoot(parents[x]);
        }

        return parents[x];
    }

    void union(int x, int y) {
        int rootOfX = findRoot(x);
        int rootOfY = findRoot(y);

        if (rootOfX == rootOfY) {
            return;
        }

        parents[rootOfX] = rootOfY;
    }


    public static void main(String[] args) {
        int N = 4;
        DisjoinSetUnionByBiggestIndex disjoinSet = new DisjoinSetUnionByBiggestIndex(N);
        disjoinSet.union(0, 1);
        disjoinSet.union(1, 2);

        // Check if 1 is in the same set with 2
        if (disjoinSet.findRoot(1) == disjoinSet.findRoot(2)) {
            System.out.println("1 is in the same set with 2");
        } else {
            System.out.println("1 is not in the same set with 2");
        }

        // Check if 1 is in the same set with 3
        if (disjoinSet.findRoot(1) == disjoinSet.findRoot(3)) {
            System.out.println("1 is in the same set with 3");
        } else {
            System.out.println("1 is not in the same set with 3");
        }
    }
}

Initial state of parents

Initial states of union by index

Final state of parents after all unionizing

Final states of union by index

Approach 2: Union by higher rank

Find with compress path and Union by higher rank

DisjoinSetUnionByRank.java

package com.hellokoding.datastructure;

public class DisjoinSetUnionByRank {
    int[] parents, ranks;
    int N;

    DisjoinSetUnionByRank(int N) {
        this.N = N;
        parents = new int[N];
        ranks = new int[N];
        initDisjoinSet();
    }

    void initDisjoinSet() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

    int findRoot(int x) {
        if (parents[x] != x) {
            parents[x] = findRoot(parents[x]);
        }

        return parents[x];
    }

    void union(int x, int y) {
        int rootOfX = findRoot(x);
        int rootOfY = findRoot(y);

        if (rootOfX == rootOfY) {
            return;
        }

        if (ranks[rootOfX] < ranks[rootOfY]) {
            parents[rootOfX] = rootOfY;
        } else if (ranks[rootOfX] > ranks[rootOfY]) {
            parents[rootOfY] = rootOfX;
        } else {
            parents[rootOfX] = rootOfY;
            ranks[rootOfY] = ranks[rootOfY] + 1;
        }
    }


    public static void main(String[] args) {
        int N = 4;
        DisjoinSetUnionByRank disjoinSet = new DisjoinSetUnionByRank(N);
        disjoinSet.union(0, 1);
        disjoinSet.union(1, 2);

        // Check if 1 is in the same set with 2
        if (disjoinSet.findRoot(1) == disjoinSet.findRoot(2)) {
            System.out.println("1 is in the same set with 2");
        } else {
            System.out.println("1 is not in the same set with 2");
        }

        // Check if 1 is in the same set with 3
        if (disjoinSet.findRoot(1) == disjoinSet.findRoot(3)) {
            System.out.println("1 is in the same set with 3");
        } else {
            System.out.println("1 is not in the same set with 3");
        }
    }
}

Initial state of parents

Initial states of union by rank

Final state of parents after all unionizing

Final states of union by rank
Follow HelloKoding