• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



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:



This is a Premium content.
Please subscribe to the Algorithms course to access the detailed Algorithm discussion.





Working Solution:

Java code:


This is a Premium content.
Please subscribe to Algorithms course to access the code.





Python code:


This is a Premium content.
Please subscribe to Algorithms course to access the code.





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



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave