😇721 account merge

https://leetcode.com/problems/accounts-merge/

感觉是很好的union find的题目，union的过程是你认为两个group需要union然后主动call union才会union，一般是by size，size相等的时候谁当组长其实不确定的，然后注意这里每一组account天然就是一个group，对应一个group id，之后可以通过这个反向找到一开始的accounts

这里最关键的是把emails展平成email->idx的形式，如果email已经存在就union当前idx和已经存在的idx，最后生成答案是通过email的idx找到对应的leader对应的account

class Solution {
    private class Union {
        int[] representatives;
        int[] size;
        
        public Union(int n) {
            size = new int[n];
            representatives = new int[n];
            for (int i = 0; i < n; i++) {
                representatives[i] = i;
                size[i] = 1;
            }
        }
        public int find(int a) {
            if (representatives[a] == a) {
                return a;
            } 
            representatives[a] = find(representatives[a]);
            return representatives[a];
        }
        //注意union不是一个自发的过程，是你点名要union这两个partition它们俩才会union
        public void union(int a, int b) {
            int ar = find(a);
            int br = find(b);
            if (size[ar] >= size[br]) {
                size[ar] += size[br];
                representatives[br] = ar;
            } else {
                size[br] += size[ar];
                representatives[ar] = br;
            }
        }
    }
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        Union uni = new Union(n);
        Map<String, Integer> map = new HashMap<>();
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account = accounts.get(i);
            for (int j = 1; j < account.size(); j++) {
                String email = account.get(j);
                if (!map.containsKey(email)) {
                    map.put(email, i);
                } else {
                    //总是与第一次遇到email时的account去union
                    uni.union(map.get(email), i);
                }
            }
        }
        // group id -> emails under the group
        // 因为可能有重名所以名字不能作为key，用group id是最好的选择
        Map<Integer, Set<String>> groups = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account = accounts.get(i);
            //这里相当于遍历了union所有的group
            int group = uni.find(i);
            Set<String> set = groups.get(group);
            if (set == null) {
                set = new HashSet<>();
            }
            groups.put(group, set);
            for (int j = 1; j < account.size(); j++) {
                String email = account.get(j);
                set.add(email);
            }
        }

        for (Map.Entry<Integer, Set<String>> entry : groups.entrySet()) {
            int group = entry.getKey();
            Set<String> emails = entry.getValue();
            List<String> account = new ArrayList<>(emails);
            Collections.sort(account);
            account.add(0, accounts.get(group).get(0));
            ans.add(account);
        }
        return ans;
    }
}

注意下面的写法会出问题

class Union {
        int[] leaders;
        public Union(int n) {
            this.leaders = new int[n];
            for (int i = 0; i < n; i++) {
                this.leaders[i] = i;
            }
        }
        public int union(int l, int r) {
            int leaderl = find(l);
            int leaderr = find(r);
            if (leaderl == leaderr) {
                return 0;
            }
            leaders[r] = leaderl;
            return 1;
        }

        public int find(int i) {
            if (leaders[i] == i) {
                return i;
            }
            leaders[i] = find(leaders[i]);
            return leaders[i];
        }
    }

如以下case：

union 1 2 leader: 1
union 1 3 leader: 1
union 0 4 leader: 0
union 3 4 leader: 1

这是由于4的leader被更新成了0，但是4的leader并非它自己而是1，可以把union看成一个森林也就是一堆树的集合，union两棵树一定要找到它的root来union，在经过find的path compression之后，每棵树都被扁平化了，也就是说1一定是root，我们要做的是把1也就是root的leader设成0而不是把4的leader设成0：

class Union {
        int[] leaders;
        public Union(int n) {
            this.leaders = new int[n];
            for (int i = 0; i < n; i++) {
                this.leaders[i] = i;
            }
        }
        public int union(int l, int r) {
            int leaderl = find(l);
            int leaderr = find(r);
            if (leaderl == leaderr) {
                return 0;
            }
            leaders[leaderr] = leaderl;
            return 1;
        }

        public int find(int i) {
            if (leaders[i] == i) {
                return i;
            }
            leaders[i] = find(leaders[i]);
            return leaders[i];
        }
    }