OA原题描述参考：

注意：具体抽到的题目可能会有细微变化。

给了一些itemAssociation, 如果一个item既在association A里面出现过，又在association B里面出现过，那么就把A和B合并成一个association。求全部合并后最大的association。

如果两个association一样大，返回lexicographic order的第一个。

input：String[][] itemAssociation

return: String[]. visit 1point3acres.com for more.

example:

input:

[itemA, itemB]

[itemB, itemC]-google 1point3acres

[itemD, itemE]

合并之后：

[itemA, itemB, itemC].,

[itemD, itemE].

第一个有三个item最多，于是返回[itemA, itemB, itemC]

解题思路参考：

类似路径问题其实DFS，BFS和UnionFind都可以解决。这个因为是求最大的集合，用unionfind复杂度最好。坑：unionfind的模板是int数组，所以要把item放到一个hashmap里面产生唯一下标。根据下标做集合合并操作。合并时候注意size的计算是两个老大直接计算。输出结果需要费点劲。

参考答案：

package com.amazon;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Tian on 2017/8/9.
 */
public class ItemAssociation {
    public static void main(String[] args) {
        String[][] items = {{"itemA", "itemB"}, {"itemB", "itemC"},
                {"itemD", "itemE"}, {"itemE", "itemF"}, {"itemG", "itemD"}};

        ItemAssociation ia = new ItemAssociation();
        String[] res = ia.count(items);
    }

    public String[] count(String[][] items) {
        int n = items.length;

        int index = 0;
        Map<String, Integer> hash = new HashMap<String, Integer>();
        for (int i = 0; i < n; i++) {
            if (!hash.containsKey(items[i][0])) hash.put(items[i][0], index++);
            if (!hash.containsKey(items[i][1])) hash.put(items[i][1], index++);
        }

        UnionFind un = new UnionFind(hash.size());

        for (int i = 0; i < n; i++) {
            un.union(hash.get(items[i][0]), hash.get(items[i][1]));
        }

        int maxIndex = un.findMaxSize();
        System.out.println(maxIndex);
        for (Map.Entry<String, Integer> entry : hash.entrySet()) {
            String key = entry.getKey();
            Integer ind = entry.getValue();
//            System.out.println(key + un.find(ind));
            if (un.find(ind) == maxIndex) {
                System.out.println(key);
            }
        }
        return null;
    }

    class UnionFind {
        int[] father = null;
        int[] size = null;
        UnionFind(int n) {
            father = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i; //father is itself
                size[i] = 1;
            }
        }

        void union(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_b] = root_a; //father merge
                size[root_a] += size[root_b];
            }
        }

        int find(int x) {
            if (father[x] == x) {
                return x;
            }

            return father[x] = find(father[x]);
        }

        int findMaxSize() {
            int max = 0;
            int index = 0;
            for (int i = 0; i < size.length; i++) {
//                System.out.println("father["+i+"]"+father[i]+" size[" +i +"]"+ size[i]);
                if (size[i] > max) {
                    max = size[i];
                    index = i;
                }
            }
            return index;
         }
    }
}