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 adirect friendof B, and B is a direct friend of C, then A is anindirect friendof C. Andwe 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:**

1 | Input: |

## Analysis

### DFS

Treat `M`

as an adjacency matrix of a graph.

1 | // 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 `marked`

array.