描述
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:
1 | Input: |
Example 2:
1 | Input: |
Note:
- N is in range [1,200].
- M[i][i] = 1 for all students.
- If M[i][j] = 1, then M[j][i] = 1.
分析
这道题本质上就是求无向图中的连通图个数。类似的题目还有 323-Number of Connected Components in an Undirected Graph(需订阅)。这里用二元数组来表示图的概念。
解决方案1(Java)
1 | class Solution { |
相关问题
- (M) Number of Connected Components in an Undirected Graph
- (E) Robot Return to Origin
- (E) Sentence Similarity
- (M) Sentence Similarity II