Minimal Vertices
Application of Topological Sort, Strongly Connected Components and Tarjan's Algorithm

Customer Support: admin@thealgorists.com

Feedback Form:
https://www.thealgorists.com/Feedback.

Manage Subscriptions:
https://www.thealgorists.com/CustomerPortal
(Make sure you are logged into https://www.thealgorists.com.)
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>5For 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
The above content is written by:
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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn