Feature #1: Friend Circles

Description

First, we need to find all the people that are in each user’s friends circle on Facebook. Your individual friend circle is defined as a group of users who are directly or indirectly friends with you. Assume there are a total of n users on Facebook. Some of them are your friends and others are not. The friendship/connection is transitive in nature. For example, if Shaw is a direct friend of Andy, and Andy is a direct friend of Noah, then Shaw is an indirect friend of Noah. Getting the total number of friend circles that exist on Facebook helps us suggest connections on Instagram for every user.

We’ll be provided with an n x n square matrix, where n is the number of users on Facebook. A cell [i,j] will hold the value 1 if user i and user j are friends. Otherwise, the cell will hold the value 0. For example, consider the input:

There are two friend circles in the above example. Shaw is friends with Andy only, but Andy is friends with both​ Shaw and Noah. These three users make one friend circle. Dana, alone, makes ...