🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement: In a certain social network, when someone gets a message he/she sends that message to all of his/her followers.
Now, I am considering to spread a promotion message across all people in that social network.

Your task is to find the minimum number of people to reach out (for example, who doesn't follow anyone etc) so that my promotion message spreads out across entire social network.

We need to consider loops like, if A follows B, B follows C, C follows D, D follows A (A -> B -> C -> D -> A) then reaching only one of them is sufficient to spread your message.

Input: List of followers for every user in the social network:

1:  3, 4
2:
3:  1
4:  3

Here, user 1 has user 3 and 4 as followers. User 2 has no followers. User 3 has user 1 s follower. User has user 3 as follower.

Output: Minimal list of people to be reached to spread out message across everyone in the network.

Tag(s): #facebook_interview

Solution:

Algorithm:

Login to Access Content

Working Solution:

Java code:

Login to Access Content




Python code:

Login to Access Content

Don't forget to take a look at other interesting Graph Problems:

• Disconnected Network
• Critical Connection
• Minimal Vertices
• Course Scheduling

Instructor: