# 1452. People Whose List of Favorite Companies Is Not a Subset of Another List
###### tags: `Leetcode` `Medium` `Union Find`
## 思路
典型的union find题目
把相互包含的favoriteCompany list放在一起，最后把所有的unique father输出出来
重点是如何将两个list combine在一起：只要一个list包含另一个，就可以合并
## Code

class Solution {
    int[] fa;
    int[] size;
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        fa = new int[favoriteCompanies.size()];
        for(int i = 0;i < favoriteCompanies.size();i++){
            fa[i] = i;
        }
        List<Integer> res = new ArrayList<>();
        List<Set<String>> fcs = new ArrayList<>();
        for(List<String> fc: favoriteCompanies){
            fcs.add(new HashSet<>(fc));
        }
        for(int i = 0; i < fcs.size(); i++){
            for(int j = i+1; j < fcs.size();j++){
                int a = find(i), b = find(j);
                if(a == b) continue;
                if(contains(fcs.get(a),fcs.get(b))) fa[b] = a;
                else if(contains(fcs.get(b),fcs.get(a))) fa[a] = b;
            }
        }
        Set<Integer> father = new HashSet<>();
        for(int i:fa){
            father.add(find(i));
        }
        res.addAll(father);
        Collections.sort(res);
        return res;
    }
    private int find(int a){
        if(fa[a] == a) return a;
        else return find(fa[a]);
    }
    private boolean contains(Set<String> a, Set<String> b){
        if(a.size() <= b.size()) return false;
        else return a.containsAll(b);
    }
}