LeetCode 323 - Number of Connected Components in an Undirected Graph

Givenn nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:

You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1] is the same as[1, 0]and thus will not appear together inedges.

Solution:

class Solution {
     public int countComponents(int n, int[][] edges) {

        if (n == 0 || edges == null || edges.length == 0)
            return 0;

        if (n == 1)
            return n;

        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();

        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        // BFS using queue
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                count++;
                queue.offer(i);

                while (!queue.isEmpty()) {
                    int cur = queue.poll();
                    visited.add(cur);

                    for(int next : graph.get(cur)) {
                        if (!visited.contains(next)) {
                            queue.offer(next);
                        }
                    }
                }
            }
        }
        return  count;
    }
}