Java 23ms Iteration Solution - Using Queue Find Connected Components In Graph


  • 0
    S

    The idea is trade the matrix as a graph. Then start at a node and using BSF. Find how many components in the graph.

    public class Solution {
        public int findCircleNum(int[][] M) {
            if(M == null || M.length <= 1){
                return 1;
            }
            int n = M.length;
            boolean[] visited = new boolean[n];
            int res = 0;
            for(int i = 0; i < n; i++){
                if(visited[i]){
                    continue;
                }
                res++;
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                while(!queue.isEmpty()){
                    int size = queue.size();
                    for(int s = 0; s < size; s++){
                        int temp = queue.poll();
                        if(visited[temp]){
                                continue;
                            }
                        for(int j = 0; j < n; j++){
                            if(M[temp][j] == 1){
                                queue.offer(j);
                            }
                        }
                        visited[temp] = true;
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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