Interview Note - Union Find

Union Find

From wiki:
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. It supports two useful operations:
Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its “representative”; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
Union: Join two subsets into a single subset.

Example:
261. Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            if (!uf.union(edges[i][0], edges[i][1])) {
                return false;
            }
        }
        return uf.size == 1;
    }
    
    private class UnionFind {
        int size;
        int[] nodes;
        
        UnionFind(int size) {
            this.size = size;
            this.nodes = new int[size];
            for (int i = 0; i < size; i++) {
                nodes[i] = i;
            }
        }
        
        boolean union(int a, int b) {
            int label_a = nodes[a];
            int label_b = nodes[b];
            if (label_a == label_b) {
                return false;
            } else {
                for (int i = 0; i < nodes.length; i++) {
                    if (nodes[i] == label_a) {
                        nodes[i] = label_b;
                    }
                }
                size--;
                return true;
            }
        }
    }
}

Read More