Lintcode 1396. Set Union

Description

There is a list composed by sets. If two sets have the same elements, merge them. In the end, there are several sets left.

• The number of sets n <=1000.
• The number of elements for each set m <= 100.
• The element must be a non negative integer and not greater than 100000.

Have you met this question in a real interview?  

Example

Example 1:

Input :list = [[1,2,3],[3,9,7],[4,5,10]]
Output:2 .
Explanation:There are 2 sets of [1,2,3,9,7] and [4,5,10] left.

Example 2:

Input:list = [[1],[1,2,3],[4],[8,7,4,5]]
Output :2 

Explanation:There are 2 sets of [1,2,3] and [4,5,7,8] left. 

Code (Java)

public class Solution {
    /**
     * @param sets: Initial set list
     * @return: The final number of sets
     */
    public int setUnion(int[][] sets) {
        // Write your code here
        if (sets == null || sets.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> parentsMap = new HashMap<>();
        int numSets = 0;
        
        // init the map 
        for (int[] set : sets) {
            for (int node : set) {
                parentsMap.put(node, node);
            }
        }
        
        numSets = parentsMap.size();
        
        // union-find 
        for (int[] set : sets) {
            for (int i = 1; i < set.length; i++) {
                int p1 = find(set[i - 1], parentsMap);
                int p2 = find(set[i], parentsMap);
                
                if (p1 != p2) {
                    parentsMap.put(p1, p2);
                    numSets--;
                }
            }
        }
        
        return numSets;
    }
    
    private int find(int node, Map<Integer, Integer> parentsMap) {
        int root = node;
        
        while (root != parentsMap.get(root)) {
            root = parentsMap.get(root);
        }
        
        // path compression 
        while (node != root) {
            int parent = parentsMap.get(node);
            parentsMap.put(node, root);
            node = parent;
        }
        
        return root;
    }
}