← 返回 openai 的题目列表Friend Circles / Number of Provinces
类型：online_judge
Friend Circles / Number of Provinces
There are n users labeled from 0 to n - 1. You are given an n × n adjacency matrix isConnected:
isConnected[i][j] == 1 means users i and j are direct friends.
isConnected[i][j] == 0 means they are not direct friends.
Every user is a friend of themselves: isConnected[i][i] == 1.
Friendship is symmetric.
If A is a friend of B and B is a friend of C, then A, B, and C belong to the same friend circle, even if A and C are not direct friends.
Return the total number of friend circles.
Example 1
Input:
3
1 1 0
1 1 0
0 0 1
Output:
2
Example 2
Input:
3
1 0 0
0 1 0
0 0 1
Output:
3
Constraints
1 <= n <= 200
isConnected is an n × n symmetric binary matrix.
Example
Input
3
1 1 0
1 1 0
0 0 1
Output
2