Amazon Online Assessment (OA) - Friend Circles

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 define a friend circle as 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.

Examples

Example 1:

Input:

[[1,1,0],
[1,1,0],
[0,0,1]]

Output: 2

Explanation :

The 0^th and 1^st students are direct friends, so they are in a friend circle.

The 2^nd student is in a friend circle. so return 2.

Example 2:

Input:

[[1,1,0],
[1,1,1],
[0,1,1]]

Output: 1

Explanation :

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.

Constraints:

• 1 <= N <= 200
• M[i][i] == 1
• M[i][j] == M[j][i]

Try it yourself