Count the Separate Friend Circles
Implement countProvinces
There are n people, and some of them are direct friends. The friendships are given as an n × n adjacency matrix: isConnected[i][j] = 1 if person i and person j are direct friends, and 0 otherwise (the matrix is symmetric and every person is a "friend" of themselves on the diagonal). A friend circle is a group of people connected through chains of direct friendships, and it cannot be enlarged with anyone else. Return the number of friend circles.
Equivalently: count the connected components of an undirected graph given as an adjacency matrix.
Example 1:
Input: isConnected = [[1,1,0,0,0,0],[1,1,0,0,1,0],[0,0,1,1,0,0],[0,0,1,1,0,0],[0,1,0,0,1,0],[0,0,0,0,0,1]]
Output: 3
Example 2:
Input: isConnected = [[1,0],[0,1]]
Output: 2
Example 3:
Input: isConnected = [[1,1,1],[1,1,1],[1,1,1]]
Output: 1
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 20 people, numbered 0 … n − 1 - ●
isConnected is an n × n adjacency matrix: isConnected[i][j] = 1 means person i and person j are direct friends, 0 means they are not. It is symmetric and isConnected[i][i] = 1 - ●
Friendship is transitive for circle purposes: a circle is a maximal group of people in which everybody is connected to everybody else through a chain of direct friends (a connected component of the friendship graph) - ●
Return the number of circles (connected components), counting a person with no friends as a circle of their own
isConnected =