八 图与搜索-并查集

431. 找无向图的连通块

https://www.lintcode.com/zh-cn/problem/connected-component-in-undirected-graph/#
这道题的思路就是用并查集。
1.首先用HASHMAP 写一个并查集
2.初始化PARENT MAP，把每个节点的父亲置为-1
3.开始对所有NEIGHBOR 做UNION（这里用UNION）
4.针对PARENT MAP，做聚集操作。（这里用FIND）
5.生成答案

Map<Integer,Integer> parent;
    public int find(int i){
        if(parent.get(i) == -1) return i;
        parent.put(i, find(parent.get(i)));
        return parent.get(i);
    }
    public boolean union(int i,int j) {
        int pi = find(i);
        int pj = find(j);
        if(pi == pj) return false;
        parent.put(pi, pj);
        return true;
    }
    public List<List<Integer>> connectedSet(List<UndirectedGraphNode> nodes) {
        //init parent
        parent = new HashMap<>();
        for(UndirectedGraphNode node : nodes){
            parent.put(node.label,-1);
        }
        
        //union
        for(UndirectedGraphNode node : nodes){
            for(UndirectedGraphNode nei : node.neighbors){
                union(node.label,nei.label);
            }
        }
        
        // for(int key : parent.keySet()){
        //     System.out.println(key+":"+parent.get(key));
        // }
        
        Map<Integer,Set<Integer>> chds = new HashMap<>();
        //get ans
        for(int key : parent.keySet()){
            if(chds.containsKey(find(key))){
                chds.get(find(key)).add(key);
            }else{
                Set<Integer> cur = new TreeSet<>();
                cur.add(key);
                chds.put(find(key),cur);
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for(Set<Integer> s : chds.values()){
            ans.add(new ArrayList<>(s));
        }
        return ans;
        
    }

178. 图是否是树

https://www.lintcode.com/zh-cn/problem/graph-valid-tree/#
1.用并查集判断无向图里是否有环
2.检查边数是否为n-1.

int[] parent;
     int find(int i){
         if(parent[i] == i) return i;
         return parent[i] = find(parent[i]);
     }
     boolean union(int i,int j) {
         int pi = find(i);
         int pj = find(j);
         if(pi == pj) return false;
         parent[pi] = pj;
         return true;
     }
    public boolean validTree(int n, int[][] edges) {
        parent = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
        if(edges.length != n-1) return false; 
        for(int[] edge : edges){
            if(!union(edge[0],edge[1])) return false;
        }
        return true;
    }

721. Accounts Merge

https://leetcode.com/problems/accounts-merge/description/
第一步构建EMAIL的并查集。
第二步 初始化MAP，同时需要一个EMAIL 2 NAME的MAP
第三步 做UNION
第四步 重新遍历每个元素，把PARENT一样的聚类成一个MAP
第五步 根据聚类的MAP生成要的ANS。

Map<String,String> parent = new HashMap<>();
    private String find(String c){
        if(parent.get(c).equals(c)) return c;
        parent.put(c,find(parent.get(c)));
        return parent.get(c);
    }
    private void union(String c1,String c2) {
        String p1 = find(c1);
        String p2 = find(c2);
        if(p1.equals(p2)) return;
        parent.put(p1,p2);
    }
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String,String> email2Name = new HashMap<>();
        for(List<String> l : accounts){
            String name = l.get(0);
            
            for(String s : l.subList(1,l.size())){
                
                parent.put(s,s);
                email2Name.put(s,name);
            }
        }
        for(List<String> l : accounts){
            for(int i=1;i<l.size()-1;i++){
                union(l.get(i),l.get(i+1));
            }
        }
        Map<String,List<String>> preans = new HashMap<>();
        for(String email : parent.keySet()){
            String p = find(email);
           // System.out.println(p);
            if(preans.containsKey(p)){
                preans.get(p).add(email);
            }else{
                List<String> cur = new ArrayList<>();
                cur.add(email);
                preans.put(p,cur);
            }
        }
        List<List<String>> ans = new ArrayList<>();
        for(String e : preans.keySet()){
            List<String> cur = new ArrayList<>();
            cur.add(email2Name.get(e));
            for(String email: preans.get(e)){
                cur.add(email);
            }
            Collections.sort(cur);
            ans.add(cur);
        }
        return ans;
        
    }

547. Friend Circles

https://leetcode.com/problems/friend-circles/description/
并查集基本操作

 int[] pa;
    private int find(int i){
        if(pa[i] == i) return i;
        return pa[i] = find(pa[i]);
    }
    private void union(int i,int j){
        int pi = find(i);
        int pj = find(j);
        pa[pi] = pj;
    }
    public int findCircleNum(int[][] M) {
        int n = M.length;
        pa = new int[n];
        for(int i=0;i<n;i++)
            pa[i] = i;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(M[i][j]==1){
                    union(i,j);
                }
            }
        }
        Set<Integer> s = new HashSet<>();
        for(int i=0;i<n;i++)
            s.add(find(i));
        return s.size();
    }

684. Redundant Connection

https://leetcode.com/problems/redundant-connection/description/

int[] parent;
    private int find(int c){
        if(parent[c] == c) return c;
        return parent[c] = find(parent[c]);
    }
    private boolean union(int c1,int c2){
        int p1 = find(c1);
        int p2 = find(c2);
        if(p1 == p2) return false;
        parent[p1] = p2;
        return true;
    }
    public int[] findRedundantConnection(int[][] edges) {
        int l = edges.length;
        parent = new int[l+1];
        for(int i=1;i<=l;i++)
            parent[i] = i;
        for(int[] edge : edges){
            if(!union(edge[0],edge[1])){
                return edge;
            }
        }
        return new int[0];
    }