672. Friend Circles
A club has n members numbered 0 to n-1. The square matrix connected records who knows whom: connected[i][j] == 1 means members i and j know each other directly, and 0 means they do not. The matrix is symmetric and every member knows themself, so connected[i][i] == 1.
A circle is a group of members in which any two people are linked by a chain of direct acquaintances, and nobody outside the group is linked to anybody inside it. Return the number of circles in the club. Use an explicit stack or queue for the traversal. The expected solution runs in O(n^2) time, which is the size of the input, and O(n) extra space.
Example 1
- Input:
- connected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]
- Output:
- 2
- Explanation:
Members 0 and 3 know each other and members 1 and 2 know each other, with no links between the two pairs, so there are 2 circles.
Example 2
- Input:
- connected = [[1,1,0],[1,1,1],[0,1,1]]
- Output:
- 1
- Explanation:
Member 1 knows both 0 and 2, so all three belong to one circle even though 0 and 2 do not know each other directly.
Constraints
1 ≤ n ≤ 500
connected[i][j] is 0 or 1, connected[i][i] == 1 and connected[i][j] == connected[j][i]
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)