Java BFS solution, easy to understand


  • 0
    F
    public int findCircleNum(int[][] M) {
    	if (M == null || M.length == 0)
    		return 0;
    	Set<Integer> visited = new HashSet<>();
    	int res = 0;
    	for (int i = 0; i < M.length; i++) {
    		if (!visited.contains(i)) {
    			visited.add(i);
    			bfs(M, visited, i);
    			res++;
    		}
    	}
    	return res;
    }
    
    private void bfs(int[][] M, Set<Integer> visited, int index) {
    	Queue<Integer> q = new LinkedList<>();
    	q.add(index);
    	while (!q.isEmpty()) {
    		int i = q.poll();
    		for (int j = 0; j < M.length; j++) {
    			if (M[i][j] == 1 && !visited.contains(j)) {
    				visited.add(j);
    				q.add(j);
    			}
    
    		}
    	}
    }

Log in to reply
 

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