Reference: LeetCode
Difficulty: Medium

## Problem

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.

Note:

• N is in range [1,200].
• M[i][i] = 1 for all students.
• If M[i][j] = 1, then M[j][i] = 1.

Example:

## Analysis

### DFS

Treat M as an adjacency matrix of a graph.

Time: $O(N^2) = O(N + M) = O(N + N^2)$ for a dense graph.
Space: $O(N)$ for marked array.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.