Minimal Vertices

• Algorithms and Data Structures: TheAlgorist.com
  
• System Design: DistributedComputing.dev
  
• Low Level Design: LowLevelDesign.io
  
• Frontend Engineering: FrontendEngineering.io
  

---

Click here to see our updates

Problem Statement:

Given a directed graph G , find the minimum number of vertices from which all nodes are reachable.
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:

• How to Send Message to Entire Social Network
• Disconnected Network
• Critical Connection
• Course Scheduling

Instructor:

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

---

Click here to see our updates