Easy dfs Java solution


  • 0
    A

    The idea is to do a dfs from each friend. Once we exhaust our search from one friend, we increase our friend circle(count) by 1 and carry out search from next friend and so on.

    public class Solution {
        public int findCircleNum(int[][] M) {
            
           //create a boolean visited array to check if node  has been visited.
           boolean [] visited = new boolean[M.length];
            int count=0;
            
            for(int i=0;i<M.length;i++)
            {
                if(!visited[i])
                {
                  //friend circle increased to 1
                  count++;
                  dfs(M,i,visited);
                }
               
            }
             return count;
        }
        
        private void dfs(int[][] M,int id,boolean[]visited)
        {
            for(int i=0;i<M.length;i++)
            {
                if(M[id][i]==1 && !visited[i] && id!=i)
                {
                    visited[i]=true;
                    dfs(M,i,visited);
                }
                
            }
        }
    }
    

Log in to reply
 

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