# Java solution using connected graph node approach

• 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;
}
``````

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