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

// 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