https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf

• Redundant Connection
• Graph Valid Tree

Union find template

//union find + path compression & union by rank
class UnionFind {
    int[] parent;
    int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    private boolean union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) return false;//connected, no need to union
        //link root of smaller tree to the root of larger tree
        if (size[root1] < size[root2]) {
            parent[root1] = root2;
            size[root2] += size[root1];
        } else {
            parent[root2] = root1;
            size[root1] += size[root2];
        }
        return true;
    }

    //find the root + path compression
    //path compression: flatten the tree. link all nodes directly to the root
    //to improve the find method running time.
    private int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }
}

Graph Valid Tree

Union find, If the two nodes have been connected, then there is a cycle.

Add 'count' field variable to track the number of component in the graph