| English | 简体中文 |

# 547. Friend Circles

## Description

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 i_{th} and j_{th} 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:**

Input:[[1,1,0], [1,1,0], [0,0,1]]Output:2Explanation:The 0_{th}and 1_{st}students are direct friends, so they are in a friend circle.

The 2_{nd}student himself is in a friend circle. So return 2.

**Example 2:**

Input:[[1,1,0], [1,1,1], [0,1,1]]Output:1Explanation:The 0_{th}and 1_{st}students are direct friends, the 1_{st}and 2_{nd}students are direct friends,

so the 0_{th}and 2_{nd}students are indirect friends. All of them are in the same friend circle, so return 1.

**Note:**

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