Problem

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

 Notice

Each connected component should sort by label.

Clarification
Learn more about representation of graphs

Example
Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E
Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

思路

1. hashset: if the node is visited.
2. iterate through the list.
   1. if visited, pass
   2. else bfs, pass a list to record the node in the connected components
      • add to the result list.

    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        List<List<Integer>> result = new ArrayList<>();
        if (nodes == null || nodes.size() == 0) {
            return result;
        }

        Set<UndirectedGraphNode> visited = new HashSet<>();
        for (UndirectedGraphNode curt: nodes) {
            if (!visited.contains(curt)) {
                List<Integer> component = bfs (curt, visited);
                result.add(component);
            }
        }
        return result;
    }

    private List<Integer> bfs (UndirectedGraphNode node, Set<UndirectedGraphNode> visited) {
        List<Integer> list = new ArrayList<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        queue.offer(node);
        visited.add(node);

        while (!queue.isEmpty()) {
            UndirectedGraphNode curt = queue.poll();
            list.add(curt.label);
            for (UndirectedGraphNode adj: curt.neighbors) {
                if (visited.contains(adj)) continue;
                queue.offer(adj);
                visited.add(adj);
            }
        }
        Collections.sort(list);
        return list;
    }