Very simple BFS Solution in JAVA..


  • 0
    I
    int findCircleNum(int[][] M) {
    	int count = 0;
    	for(int i=0;i<M.length;i++){
    		if(M[i][i]==1){
    			count++;
    			bfs(i, M);
    		}
    	}
    	return count;
    }
    	
    private void bfs(int i, int[][] M){
    	Queue<Integer> q = new LinkedList<>();
    	q.add(i);	
    	while(!q.isEmpty()){
    		int curr = q.poll();
    		M[curr][curr] = 2;	//Marking as visited
    		for(int k = 0;k<M.length;k++){
    			if(M[k][k]==1 && M[curr][k]==1){
    				q.add(k);
    			}
    		}
    	}
    }
    

Log in to reply
 

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