Java dfs search, 13ms


  • 0
    S

    This problem is equivalent to finding the number of connected component problem in an undirect graph, which can be solved with dfs.

    i=0 to M.length -1 can be regarded as vertices. M[i][j] == 1 means there is an edge between vertex i and vertex j.

    At first, all vertex are marked as unvisited. Starting from any unvisited vertex, perform dfs on it. While performing dfs, we mark the vertex on the path as visited. At the end of the dfs, all vertices that are in the same connected component will all be marked as "visited".

    Then we check if any vertex is still unvisited. If true, it means there is at least another friend circle. Repeat dfs on unvisited vertex to find it out.

    public class Solution {
        public int findCircleNum(int[][] M) {
            int count = 0;
            int[] visited = new int[M.length];
            
            for(int i = 0; i < visited.length; i++){
                if(visited[i] == 0){
                    //means there is a undiscovered connected component  containing vertex i. 
                    count++;
                    //At the end of dfs, all vertices within the same connected component with vertex i will be marked as visited.
                    dfs(M, i, visited);
                }
            }
              
            return count;  
        }
        
        
        private void dfs(int[][] graph, int vertex, int[] visited){
            //first, mark vertex as visited  
            visited[vertex] = 1;
            for(int i = 0; i < graph.length; i++){
                //recursively perform dfs on unvisited vertex's connected neighbors.
                if(visited[i] == 0 && graph[vertex][i] == 1){
                    dfs(graph, i, visited); 
                }
            }
        } 
    }
    

Log in to reply
 

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