• 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:

Given a directed graph G , find the minimum number of vertices (let's call these vertices minimal vertices) from which all nodes are reachable. Print these minimal vertices.
For example:
          0<-------1
                  _
            \     /|
            _\|  /
               2

               |
              \ /

               3 _
             /  |\
           |/_    \
            4----->5


The above graph would have only one 1 minimal vertex: either vertex 1, 2 or 3. You can reach all the vertices if you 'start traversing from either vertex 1 , 2 or 3.

          0<-------1
                  _
            \     /|
            _\|  /
               2

              / \
               |
               3
               |
              \ /

               6 _
             /  |\
           |/_    \
            4----->5
For the above graph all the nodes are reachable from vertex 3.

Tag(s): #airbnb_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