Item Association

题目地址：
http://www.1point3acres.com/bbs/thread-283632-1-1.html

题目：
Find the biggest size of union,  if the same size, return the first one order by lex
String[] maxAssociation(String[][] associations){}

example 
input
[itemA, itemB],
[itemB, itemC],.
[itemG, itemD],
[itemD, itemF];
-->[itemA, itemB, itemC]  , [itemG, itemD, itemF]
output:
[itemA, itemB, itemC];. 


解题思路：
这道题就是用Union的方法来解决。


代码：

public class ItemAssociation {

    public static void main(String[] args){
        ItemAssociation itemAssociation = new ItemAssociation();
        String[][] input = new String[4][2];
        input[0] = new String[]{"itemA", "itemB"};
        input[1] = new String[]{"itemC", "itemB"};
        input[2] = new String[]{"itemG", "itemD"};
        input[3] = new String[]{"itemD", "itemF"};
        List<List<Character>> rst = itemAssociation.maxAssociation(input);
        System.out.println(rst);
    }

    public List<List<Character>> maxAssociation(String[][] associations){
        int[] group = new int[26];
        if(associations == null || associations.length == 0 || associations[0].length == 0){
            return null;
        }
        Arrays.fill(group, -1);
        for(int i = 0; i <= associations.length - 1; i++){
            int root = -1;
            // set the root and if there are more than two root, just the root other than the first root to be the first root.            for(int j = 0; j <= associations[0].length - 1; j++){
                int index = getIndex(associations[i][j]);
                if(group[index] != -1 && group[index] == index){
                    if(root == -1){
                        root = index;
                    }
                    else{
                        group[index] = root;
                    }
                }
                else if(group[index] != -1 && group[index] != index){
                    root = findRoot(group, index);
                }
            }
            for(int j = 0; j <= associations[0].length - 1; j++){
                if(root == -1){
                    // no root has been set for the first loop                    int index = getIndex(associations[i][j]);
                    root = index;
                    group[index] = index;
                }
                else{
                    int index = getIndex(associations[i][j]);
                    group[index] = root;
                }
            }
        }
        List[] set = new List[26];
        int max = 0;
        for(int i = 0; i <= 25; i++){
            int index = -1;
            int root = -1;
            if(group[i] != -1){
                if(group[i] == i){
                    index = i;
                    root = i;
                }
                else{
                    index = i;
                    root = findRoot(group, i);
                }
                if(set[root] == null){
                    set[root] = new ArrayList<Character>();
                }
                set[root].add(index);
                max = Math.max(max, set[root].size());
            }
        }
        List<List<Character>> rst = new ArrayList<>();
        for(int i = 0; i <= 25; i++){
            if(set[i] != null && set[i].size() == max){
                rst.add(set[i]);
            }
        }
        return rst;
    }

    private int findRoot(int[] group, int index) {
        while(index != group[index]){
            index = group[index];
        }
        return index;
    }

    private int getIndex(String s){
        char c = s.charAt(s.length() - 1);
        int index = c - 'A';
        return index;
    }

}