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
Try it yourself
Solution
Title
Script
Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem
Ipsum
has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.
Contrary to popular belief, Lorem
Ipsum
is not simply random text.
1 >>> a = [1, 2, 3] 2 >>> a[-1] 3 3