数据结构 笔记 part2

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Map<UndirectedGraphNode, Boolean> visited = new HashMap<UndirectedGraphNode, Boolean>();
        
        for (UndirectedGraphNode node : nodes) {
            visited.put (node, false);
        }

        for (UndirectedGraphNode node : nodes){
            if (visited.get(node) == false){
                bfs(node, visited, result);
            }
        }
        return result;
    }
    private static void bfs(UndirectedGraphNode node, Map<UndirectedGraphNode, Boolean> visited, List<List<Integer>> result) {
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        List<Integer> row = new ArrayList<>();
        
        visited.put(node, true);
        queue.offer(node);
        while (!queue.isEmpty()) {
            UndirectedGraphNode u = queue.poll();
            row.add(u.label);
            for (UndirectedGraphNode temp : u.neighbors) {
                if (visited.get(temp) == false) {
                    queue.offer(temp);
                    visited.put(temp, true);
                }
            }
        }
        Collections.sort(row);
        result.add(row);
    }
}

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    class UnionFind {
        HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
        UnionFind(HashSet<Integer> set) {
            for (Integer temp : set) {
                father.put(temp, temp);
            }
        }
     
        int find(int target) {
            while (father.get(target) != target) {
                target = father.get(target);
            }
            return target;
        }
        
        void union(int x, int y) {
            int fa_x = find(x);
            int fa_y = find(y);
            if (fa_x != fa_y) {
                father.put(fa_x, fa_y);
            }
        }
    }
    public List<List<Integer>> generateRes(HashSet<Integer> hashSet, UnionFind uf, int n) {
            List<List<Integer>> ans = new ArrayList<List<Integer> >();
            HashMap<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();
            for (int i : hashSet) {
                int fa = uf.find(i);
                if (!hashMap.containsKey(fa)) {
                    hashMap.put(fa, new ArrayList<Integer>());
                }
                List<Integer> now = hashMap.get(fa);
                now.add(i);
                hashMap.put(fa, now);
            }
            for (List<Integer> now : hashMap.values()) {
                Collections.sort(now);
                ans.add(now);
            }
            return ans;
        }
    
    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        // Write your code here
        HashSet<Integer> hashSet = new HashSet<Integer>();
        for (UndirectedGraphNode now : nodes) {
            hashSet.add(now.label);
        }
        UnionFind uf = new UnionFind(hashSet);

        for (UndirectedGraphNode now : nodes) {
            for (UndirectedGraphNode neighbour : now.neighbors) {
                int fnow = uf.find(now.label);
                int fneighbour = uf.find(neighbour.label);
                if (fnow != fneighbour) {
                    uf.union(now.label, neighbour.label);
                }
            }
        }
        return generateRes(hashSet, uf, nodes.size());
    }
}

 public int find(int target){
        int parent = target;
        while(parent != map.get(parent)){
            parent = map.get(parent);
        }
        int current = target;
        int next;
        while (current != map.get(current)) {
            next = map.get(current);
            map.put(current, parent);
            current = next;
        }
        return parent;

    }