Easy to understand BFS Java O(n) accepted solution.


  • 0
    S

    The idea is to explore the connected points (forming an island), either by BFS or DFS. Each time a new island is found, increase the count.

    public class Solution {
        public int countComponents(int n, int[][] edges) {
            if (n == 0) return 0;
            
            // construct a graph
            List<List<Integer>> connects = new ArrayList<List<Integer>>();
            for (int i = 0; i < n; i++) 
                connects.add(new ArrayList<Integer>());
            for (int[] edge : edges)    {
                int a = edge[0], b = edge[1];
                connects.get(a).add(b);
                connects.get(b).add(a);
            }
    
            // then visit
            int numIslands = 0;
            boolean []visited = new boolean[n];
            Queue<Integer> frontier = new LinkedList<Integer>();
            for (int i = 0; i < n; i++) {
                if (visited[i]) continue;
                // found a new island
                numIslands++;
                
                // explore the island starting from i
                frontier.add(i);
                while (!frontier.isEmpty()) {
                    int p = frontier.remove();
                    if (visited[p]) continue;
                    visited[p] = true;
                    
                    List<Integer> connect = connects.get(p);
                    for (int q : connect)   {
                        if (visited[q]) continue;
                        frontier.add(q);
                    }
                }
            }
            
            return numIslands;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.