# Union Find

## Union Find

## 1. Introduction

Union Find is an algorithm to handle **disjoint set** problems. The idea of it is to assume each set is individual at first, and based on the relations provided, we can **union** two sets. There are two operations for Union-Find:

**Find:** Determine which set a particular element is in. This can be used for determining if two elements are in the same subset.

**Union:** Join two sets into a single set.

## 2. Implementation

```java
// Weighted Union Find
class UnionFind {
        int[] sets;   // number of individual sets
        int[] size;   // size of each set

        public UnionFind(int n) {
            sets = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                sets[i] = i;
                size[i] = 1;
            }
        }

        public int find(int[] sets, int node) {
            while (node != sets[node]) {
                node = sets[node];
            }
            return node;
        }

        public void union(int node1, int node2) {
            int p = find(sets, node1);
            int q = find(sets, node2);

            // node1 and node2 are in the same set
            if (p == q) {
                return;
            }

            // merge set with smaller size into set with larger size
            if (size[p] < size[q]) {
                sets[p] = q;
                size[q] += size[p];
            }
            else {
                sets[q] = p;
                size[p] += size[q];
            }
        }
}
```

## 3. Time & Space Complexity

(1) Unweighted Union-Find:

* Find(): O(n), where n is  the number of elements
* Union(): O(n)

(2) Weighted Union-Find:

* Find(): O(logn)
* Union(): O(logn)

(3) Space: O(n)

## 4. Use of Union-Find

(1) Find the number of sets

(2) Find the set with max/min size

(3) Check cycle in undirected graph