LintCode805. Maximum Association

Amazon sells books, every book has books which are strongly associated with it. Given ListA and ListB,indicates that ListA [i] is associated with ListB [i] which represents the book and associated books. Output the largest set associated with each other(output in any sort). You can assume that there is only one of the largest set.

Example
Given ListA = ["abc","abc","abc"], ListB = ["bcd","acd","def"], return["abc","acd","bcd","dfe"].

Explanation:
abc is associated with bcd, acd, dfe, so the largest set is the set of all books

这道题使用并查集来做，我们首先做的是把散乱的集合依靠系数对应关系最终把所有可以合并的集合合并起来，然后统计每个集合的大小，找到最大的集合，然后输出这个集合的字符串

字符串所属的集合用一个整数id来表示用map<string, Integer>，同时建立id对应的string的map。

利用并查集不断去找到每个id的父id， 最后看所有id里哪个id以父id形式出现次数最多。代码如下

public class Solution {
    /**
     * @param ListA: The relation between ListB's books
     * @param ListB: The relation between ListA's books
     * @return: The answer
     */
    public int find(int id, int[] f){
        if(f[id] != id){
            f[id] = find(f[id], f);
        }
        return f[id];
    }
    public List<String> maximumAssociationSet(String[] ListA, String[] ListB) {
        // Write your code here
       
       Map<String, Integer> map = new HashMap<>();
       Map<Integer, String> name = new HashMap<>();
       int n = 0;
       for(int i = 0; i < ListA.length; i++){
           if(!map.containsKey(ListA[i])){
               map.put(ListA[i], n);
               name.put(n, ListA[i]);
               n++;
           }
           if(!map.containsKey(ListB[i])){
               map.put(ListB[i], n);
               name.put(n,ListB[i]);
               n++;
           }
       }
       
       int[] f = new int[n];
       
       for(int i = 0; i < n; i++){
           f[i] = i;
       }
       
       for(int i = 0; i < ListA.length; i++){
           int fa = find(map.get(ListA[i]), f);
           int fb = find(map.get(ListB[i]), f);
           
           if(fa != fb){
               f[fa] = fb;
           }
       }
       int[] sum = new int[n];
       int v = 0;int idx = 0;
       
       for(int i = 0; i < n; i++){
           f[i] = find(f[i], f);
           sum[f[i]]++;
           if(sum[f[i]] > v){
               v = sum[f[i]];
               idx = f[i];
           }
       }
       List<String> res = new ArrayList<>();
       for(int i = 0; i < f.length; i++){
           if(f[i] == idx){
               res.add(name.get(i));
           }
       }
       return res;
    }
}