Twitter Online Assessment (OA) 2021 | Social Network
In a social media website (which is probably Twitter, if you are wondering), there are a total
of n users. Each user can follow any number of other users. Let f be a matrix of
relationship between these users, where f[i][j] is either 0 or 1. A 1 indicates
that person i (starting from 0) is following person j, while 0 means otherwise.
In this question, we assume that each person is following themselves, and following is
symmetrical. That is, if i follows j, then j follows i. We can then define
a "group" of people. A "group" of people are people that follow each other, either directly
or indirectly. For example, if user 0 follows user 1, and user 1 follows user 2,
user 0 follows 2 indirectly.
Question: How many groups are among these n people?
Parameter
f: An integer matrix representing the relationship matrix between the users.
Result
- An integer representing the number of groups among these people.
Examples
Example 1:
Input:
1f = [ 2 [1, 1, 0], 3 [1, 1, 0], 4 [0, 0, 1], 5]
Output: 2
Explanation: There are 2 groups: User 0, 1 and user 2. User 0 and 1 are in a group
because they follow each other.
Constraints
1 <= n <= 300