431.找无向图的连通块

描述

找出无向图中所有的连通块。
图中的每个节点包含一个label属性和一个邻接点的列表。（一个无向图的�连通块是一个子图，其中任意两个顶点通过路径相连，且不与整个图中的其它顶点相连。）

注意事项

每个连通块内部应该按照label属性排序

说明

Learn more about representation of graphs

样例

给定图:

    A------B  C
     \     |  | 
      \    |  |
       \   |  |
        \  |  |
          D   E

返回 {A,B,D}, {C,E}。其中有 2 个连通块，即{A,B,D}, {C,E}

注意事项

每个连通块内部应该按照label属性排序

思路

本题bfs的做法还是比较容易理解的，先给所有结点做一个false标记，然后用for循环遍历所有点标记为false的点，从一个点开始进行bfs找到所有能找到的点，将找到的点标记为true；结果加到数组排序

代码

1. bfs

/**
 *  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(List<UndirectedGraphNode> nodes) {
        List<List<Integer>> results = new ArrayList<>();
        Map<UndirectedGraphNode, Boolean> visited = new HashMap<>();
        
        if (nodes.size() == 0) {
            return results;
        }
        
        for (int i = 0; i < nodes.size(); i++) {
            visited.put(nodes.get(i), true);
        }
        
        for (int i = 0; i < nodes.size(); i++) {
            UndirectedGraphNode node = nodes.get(i);
            if (visited.get(node) == true) {
                bfs(node, visited, results);
            }
        }
        
        return results;
    }
    
    private void bfs(UndirectedGraphNode node, 
                     Map<UndirectedGraphNode, Boolean> visited, 
                     List<List<Integer>> results) {
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        List<Integer> level = new ArrayList<>();
        
        queue.offer(node);
        visited.put(node, false);
        while (!queue.isEmpty()) {
            UndirectedGraphNode head = queue.poll();
            level.add(head.label);
            for (UndirectedGraphNode neighbor : head.neighbors) {
                if (visited.get(neighbor) == true) {
                    queue.offer(neighbor);
                    visited.put(neighbor, false);
                }
            }
        }
        Collections.sort(level);
        results.add(level);
    }
}

2. 并查集

public
class Solution {
    class UnionFind {
        HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
        UnionFind(HashSet<Integer> hashSet)
        {
            for (Integer now : hashSet) {
                father.put(now, now);
            }
        }
        int find(int x)
        {
            int parent = father.get(x);
            while (parent != father.get(parent)) {
                parent = father.get(parent);
            }
            return parent;
        }
        int compressed_find(int x)
        {
            int parent = father.get(x);
            while (parent != father.get(parent)) {
                parent = father.get(parent);
            }
            int next;
            while (x != father.get(x)) {
                next = father.get(x);
                father.put(x, parent);
                x = next;
            }
            return parent;
        }

        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);
        }
    }
    
    List<List<Integer> > print(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);
            for (UndirectedGraphNode neighbour : now.neighbors) {
                hashSet.add(neighbour.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 print(hashSet, uf, nodes.size());
    }
}