> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/finding/union-find-algorithms.md).

# Union-Find Algorithms

## Scientific method

Steps to develop a usable algorithm using scientific method:

1. Define the problem.
2. Find an algorithm to solve it.
3. Fast enough?
4. If not, figure out why.
5. Find a way to address the problem.
6. Iterate until satisfied.

## Dynamic connectivity

Given set of N objects we support two operations:

* Union command, that connects two objects
* Find connected objects command, that fins if two objects are connected

![](/files/-M3xQwOYqGEcxx-ZAWuz)Another connectivity example. ![](/files/-M3xQwO_-bbK_cVc3ZN0)

## Modeling the connections

![](/files/-M3xQwObDJD9hynVoJnn)If we connect 1 and 2, we need to recreate groups of connected points.![](/files/-M3xQwOdDrUSNl30zPd3)

## Quick-Find - eager approach

The elements are connected if the have the same number in an array.

![](/files/-M3xQwOfZ36lKMFG_NiM)

## Union

In order to union (connect the points) we need to change all from id\[p] to id\[q].

![](/files/-M3xQwOh5AKBsUHAERXM)

## Java implementation

Cost model: initialize O(n), union O(n), find O(1). Takes n^2 array accesses to process sequence of N union commands on N objects. It is too slow and we can't accept that, quick-find is too slow.

```
import java.util.Arrays;

class UF {
    private int[] id;

    public UF(int n) {
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(id);
    }

    public void union(int p, int q) {
        int pId = id[p];
        id[p] = id[q];
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId) {
                id[i] = id[p];
            }
        }
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }
}

public class UnionFind {

    public static void main(String[] args) {
        UF uf = new UF(10);
        System.out.println(uf);

        uf.union(4, 3);
        System.out.println(uf);

        uf.union(3, 8);
        System.out.println(uf);

        uf.union(6, 5);
        System.out.println(uf);

        uf.union(9, 4);
        System.out.println(uf);

        uf.union(2, 1);
        System.out.println(uf);

        uf.union(8, 9);
        System.out.println(uf);

        boolean connected89 = uf.connected(8, 9);
        System.out.println(connected89);

        boolean connected50_1 = uf.connected(5, 0);
        System.out.println(connected50_1);

        uf.union(5, 0);
        System.out.println(uf);

        boolean connected50_2 = uf.connected(5, 0);
        System.out.println(connected50_2);

        boolean connected49 = uf.connected(4, 9);
        System.out.println(connected49);
    }
}
```

It prints out:

```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
[0, 1, 2, 8, 8, 5, 6, 7, 8, 9]
[0, 1, 2, 8, 8, 5, 5, 7, 8, 9]
[0, 1, 2, 8, 8, 5, 5, 7, 8, 8]
[0, 1, 1, 8, 8, 5, 5, 7, 8, 8]
[0, 1, 1, 8, 8, 5, 5, 7, 8, 8]
true
false
[0, 1, 1, 8, 8, 0, 0, 7, 8, 8]
true
true
```

## Quick-union - lazy approach

We create tree structure. Before we connect two dots, we need to find root of the dot we want to connect to.![](/files/-M3xQwOjNSr-DAcLpCIW)Here is an example of a tree with its array.![](/files/-M3xQwOlt0ivSjJ16Mpb)Java implementation:

```
import java.util.Arrays;

class QU {
    private int[] id;

    public QU(int n) {
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(id);
    }

    public void union(int p, int q) {
        System.out.println(p + ", " + q);
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public int root(int index) {
        while (index != id[index]) {
            index = id[index];
        }
        return index;
    }
}

public class QuickUnion {

    public static void main(String[] args) {
        QU uf = new QU(10);
        System.out.println(uf);

        uf.union(4, 3);
        System.out.println(uf);

        uf.union(3, 8);
        System.out.println(uf);

        uf.union(6, 5);
        System.out.println(uf);

        uf.union(9, 4);
        System.out.println(uf);

        uf.union(2, 1);
        System.out.println(uf);

        uf.union(8, 9);
        System.out.println(uf);

        boolean connected89 = uf.connected(8, 9);
        System.out.println(connected89);

        boolean connected50_1 = uf.connected(5, 0);
        System.out.println(connected50_1);

        uf.union(5, 0);
        System.out.println(uf);

        boolean connected50_2 = uf.connected(5, 0);
        System.out.println(connected50_2);

        boolean connected49 = uf.connected(4, 9);
        System.out.println(connected49);
    }
}
```

Here is the output.

```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
4, 3
[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
3, 8
[0, 1, 2, 8, 3, 5, 6, 7, 8, 9]
6, 5
[0, 1, 2, 8, 3, 5, 5, 7, 8, 9]
9, 4
[0, 1, 2, 8, 3, 5, 5, 7, 8, 8]
2, 1
[0, 1, 1, 8, 3, 5, 5, 7, 8, 8]
8, 9
[0, 1, 1, 8, 3, 5, 5, 7, 8, 8]
true
false
5, 0
[0, 1, 1, 8, 3, 0, 5, 7, 8, 8]
true
true
```

Quick-union is also slow. Intialize O(n), union O(n) - but N depends on depth of tree, if tree is too deep, algorithm will perform slowly, find O(n).

## Quick-union improvements

### Improvement 1: Weighting

Link root of smaller tree to root of larger tree.![](/files/-M3xQwOn3Xf8MrAoHfKv)Here is the result of weighting in bigger scope.![](/files/-M3xQwOp2HAk6t_bcvEs)Java implementation:

```
import java.util.Arrays;

class WQU {

    private int[] indicies; // just to keep visual track of values in arrays
    private int[] ids;
    private int[] weights;

    public WQU(int n) {
        indicies = new int[n];
        ids = new int[n];
        weights = new int[n];
        for (int i = 0; i < n; i++) {
            indicies[i] = i;
            ids[i] = i;
            weights[i] = 1;
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(indicies) + "\n" +
                Arrays.toString(weights) + "\n" +
                Arrays.toString(ids) + "\n";
    }

    public int root(int i) {
        while (i != ids[i]) {
            i = ids[i];
        }
        return i;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        System.out.println(p + ", " + q);
        int i = ids[p];
        int j = ids[q];
        if (i == j) {
            // this means they are the same
            return;
        }
        if (weights[i] < weights[j]) {
            ids[i] = j;
            weights[j] += weights[i];
        } else {
            ids[j] = i;
            weights[i] += weights[j];
        }

    }
}

public class WeightedQuickUnion {

    public static void main(String[] args) {
        WQU uf = new WQU(10);
        System.out.println(uf);

        uf.union(4, 3);
        System.out.println(uf);

        uf.union(3, 8);
        System.out.println(uf);

        uf.union(6, 5);
        System.out.println(uf);

        uf.union(9, 4);
        System.out.println(uf);

        uf.union(2, 1);
        System.out.println(uf);

        uf.union(8, 9);
        System.out.println(uf);

        boolean connected89 = uf.connected(8, 9);
        System.out.println(connected89);

        boolean connected50_1 = uf.connected(5, 0);
        System.out.println(connected50_1);

        uf.union(5, 0);
        System.out.println(uf);

        boolean connected50_2 = uf.connected(5, 0);
        System.out.println(connected50_2);

        boolean connected49 = uf.connected(4, 9);
        System.out.println(connected49);
    }
}
```

Here is the output, observe how values are linked in the array.

```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4, 3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
[0, 1, 2, 4, 4, 5, 6, 7, 8, 9]

3, 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 3, 1, 1, 1, 1, 1]
[0, 1, 2, 4, 4, 5, 6, 7, 4, 9]

6, 5
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 3, 1, 2, 1, 1, 1]
[0, 1, 2, 4, 4, 6, 6, 7, 4, 9]

9, 4
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 4, 1, 2, 1, 1, 1]
[0, 1, 2, 4, 4, 6, 6, 7, 4, 4]

2, 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
[0, 2, 2, 4, 4, 6, 6, 7, 4, 4]

8, 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
[0, 2, 2, 4, 4, 6, 6, 7, 4, 4]

true
false
5, 0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 3, 1, 1, 1]
[6, 2, 2, 4, 4, 6, 6, 7, 4, 4]

true
true
```

Initialize O(n), union O(log2n), connect O(log2n).

### Improvement 2: Path Compression

As we go up through the tree, we flatten the tree by putting the node below the root.![](/files/-M3xQwOr2MebYBW42MA7)Java implementation (only this line `ids[i] = ids[ids[i]];` has been added to `root` method).

```
package algorithms;

import java.util.Arrays;

class PathCompWQU {

    private int[] indicies; // just to keep visual track of values in arrays
    private int[] ids;
    private int[] weights;

    public PathCompWQU(int n) {
        indicies = new int[n];
        ids = new int[n];
        weights = new int[n];
        for (int i = 0; i < n; i++) {
            indicies[i] = i;
            ids[i] = i;
            weights[i] = 1;
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(indicies) + "\n" +
                Arrays.toString(weights) + "\n" +
                Arrays.toString(ids) + "\n";
    }

    public int root(int i) {
        while (i != ids[i]) {
            ids[i] = ids[ids[i]];
            i = ids[i];
        }
        return i;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        System.out.println(p + ", " + q);
        int i = ids[p];
        int j = ids[q];
        if (i == j) {
            // this means they are the same
            return;
        }
        if (weights[i] < weights[j]) {
            ids[i] = j;
            weights[j] += weights[i];
        } else {
            ids[j] = i;
            weights[i] += weights[j];
        }

    }
}

public class PathCompressionQuickUnion {

    public static void main(String[] args) {
        PathCompWQU uf = new PathCompWQU(10);
        System.out.println(uf);

        uf.union(4, 3);
        System.out.println(uf);

        uf.union(3, 8);
        System.out.println(uf);

        uf.union(6, 5);
        System.out.println(uf);

        uf.union(9, 4);
        System.out.println(uf);

        uf.union(2, 1);
        System.out.println(uf);

        uf.union(8, 9);
        System.out.println(uf);

        boolean connected89 = uf.connected(8, 9);
        System.out.println(connected89);

        boolean connected50_1 = uf.connected(5, 0);
        System.out.println(connected50_1);

        uf.union(5, 0);
        System.out.println(uf);

        boolean connected50_2 = uf.connected(5, 0);
        System.out.println(connected50_2);

        boolean connected49 = uf.connected(4, 9);
        System.out.println(connected49);
    }
}
```

Here is the output of that program.

```
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4, 3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
[0, 1, 2, 4, 4, 5, 6, 7, 8, 9]

3, 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 3, 1, 1, 1, 1, 1]
[0, 1, 2, 4, 4, 5, 6, 7, 4, 9]

6, 5
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 3, 1, 2, 1, 1, 1]
[0, 1, 2, 4, 4, 6, 6, 7, 4, 9]

9, 4
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 1, 1, 4, 1, 2, 1, 1, 1]
[0, 1, 2, 4, 4, 6, 6, 7, 4, 4]

2, 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
[0, 2, 2, 4, 4, 6, 6, 7, 4, 4]

8, 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 2, 1, 1, 1]
[0, 2, 2, 4, 4, 6, 6, 7, 4, 4]

true
false
5, 0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 1, 2, 1, 4, 1, 3, 1, 1, 1]
[6, 2, 2, 4, 4, 6, 6, 7, 4, 4]

true
true
```

Insert O(n), union(log2\*n) - iterative logarithm, find O(log2n). Simply said, what would take 30 years to compute, it can be done in 6 seconds when using Weighted-Path-Compressed Quick-Union.

## Percolation

Percolates if there is a way from to to bottom. This model is used in electricity, fluid flow, social interactions and so on. ![](/files/-M3xQwOtiSwGJKSMWpcK)Here is how we represent the model. ![](/files/-M3xQwOv6TVVynMHuEsy) More about the problem to solve is [here](http://coursera.cs.princeton.edu/algs4/assignments/percolation.html).