Java solution using connected graph node approach


  • 0
    C

    This problem is same as find the number of nodes connected in a bidirectional graph.

    public int findCircleNum(int[][] M) {
            // maintains the association of transitive association of friends
            int[] arr = new int[M.length];
            
            for(int i=0; i<arr.length; i++){
                arr[i] = i;
            }
            
            int friendCircleCount = arr.length;
            for(int i=0; i<M.length; i++){
                for(int j=0; j<M[0].length; j++){
                    // if there is a friendship 
                    if(M[i][j] == 1){
                        // find parent of first friend circle
                        int parent1 = findParent(arr, i);
                        // find parent of second friend circle
                        int parent2 = findParent(arr, j);
                        
                        // if the parent of two different friend circle are separate then its time to merge them
                        if(parent1 != parent2){
                            arr[parent2] = arr[parent1];
                            friendCircleCount --;
                        }
                    }
                }
            }
            
            return friendCircleCount;
        }
        
        // finds the parent of a friend circle
        private int findParent(int[] arr, int idx){
            while(arr[idx] != idx){
                idx = arr[idx];
            }
            
            return idx;
        }
    

Log in to reply
 

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