547. Friend Circles
Nstudents 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.
N * N matrix
M representing the friend relationship between students in the class. If
M[i][j] = 1, then the
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.
Nis in range
M[i][i] = 1for all students.
M[i][j] = 1, then
M[j][i] = 1.
M as an adjacency matrix of a graph.
// treat this matrix as an adjacency matrix
Time: $O(N^2) = O(N + M) = O(N + N^2)$ for a dense graph.
Space: $O(N)$ for