Find the Connected Component in the Undirected Graph

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.)

Each connected component should sort by label.

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}.

Solution:

1. pick an unvisited node
2. use breadth first search to travel a connected graph and mark all visited nodes
3. repeat step 1, 2 until there is no unvisited node left.

Trick: Finding a node is unvisited or not could be done in O(1) with HashMap.

Code:

//version 1
public class Solution {

    public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
        List<List<Integer>> res = new ArrayList<>();
        if (nodes == null) {
            return res;
        }
        HashMap<Integer, Boolean> visited = new HashMap<>();
        for (UndirectedGraphNode x : nodes) {
            visited.put(x.label, false);
        }
        for (UndirectedGraphNode x : nodes) {
            if (!visited.get(x.label)) {
                bfs(x, visited, res);
            }
        }
        return res;
    }

    private void bfs(UndirectedGraphNode node, 
                HashMap<Integer, Boolean> visited, List<List<Integer>> res) {
        List<Integer> list = new ArrayList<>();
        Queue<UndirectedGraphNode> q = new LinkedList<>();
        q.offer(node);
        visited.put(node.label, true);
        while (!q.isEmpty()) {
            UndirectedGraphNode temp = q.poll();
            list.add(temp.label);
            for (UndirectedGraphNode x : temp.neighbors) {
                if (!visited.get(x.label)) {
                    q.offer(x);
                    visited.put(x.label, true);
                }
            }
        }
        Collections.sort(list);
        res.add(list);
    }
}