🙏

জয়  শ্রী  রাম

🕉

---

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:

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:

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

Instructor: