20 lines easy to understand BFS solution with Iterative


  • 0
    G
    class Solution {
        public int findCircleNum(int[][] M) {
            int res = 0;
            Set<Integer> set = new HashSet<>(); //record the students who have been in circles
            
            for (int i = 0; i < M.length; ++i) {
                if (set.contains(i)) continue; //pass the students who have been in circles
                Queue<Integer> temp = new PriorityQueue<>(); //record each circle
                temp.add(i);
                while (!temp.isEmpty()) { //find all students in a circle
                    int start = temp.poll();
                    for (int j = 1; j < M.length; ++j) { //bfs
                        if (M[start][j] == 1 && !set.contains(j)) {
                            temp.add(j);
                            set.add(j);
                        }
                    }
                }
                res++;
            }
            
            return res;
        }
    }

Log in to reply
 

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