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

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.
 If you are a student, email to admin@thealgorists.com to get special student discount.
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:
Let's look at 3 different graphs below:
The minimal vertices are marked in RED. If you start traversing from all the RED vertices you would eventually reach all other vertices in the directed graphs.
What's the common characteristics you notice for all the vertices marked in red ? They all have no inbound edges. Basically if you do a Topological Sort of all the vertices in the given directed graph, you need to include only those vertices which have indegree = 0 and are located all the way left in the topologically sorted list (i.e, towards the beginning of the topologically sorted list). Vertices with indegree = 0 are the vertices that have no inbound edges. These are the vertices which are minimal vertices and all other vertices are reachable at least from any one of these minimal vertices.
Presence of Strongly Connected Component(s):
What's missing from the directed graphs in the above diagram is Strongly Connected Components. Please read the chapter Strongly Connected Components (SCC) to know more about it.
A very important observation here is that all the vertices belonging to a Strongly Connected Component has nonzero indegree since all of them have at least one inbound edge.
These Strongly Connected Components (SCC) can be of two types:

Isolated SCC, i.e, SCC with no incoming crossedge or a forward edge from a vertex that is not part of the same SCC:
This kind of SCCs are totally disconnected from the rest of the graph, and cannot be reached from a node outside of the SCC or from other SCC. In this case we just need to make the indegree for the root of the Strongly Connected Component zero and include that in our list of minimal vertices. The SCC below is an isolated SCC.

SCC reachable from some other vertex which is not part of the same SCC:
This kind of Strongly Connected Component is connected to the rest of the graph by one or more vertices outside of the SCC (through forward edge) or from any other SCC (through crossedge). In this case there is at least one crossedge or forward edge from a node that is not part of this SCC.
In this case we do not need to include any of the vertices in the SCC in our list of minimal vertices , since all the SCC (and all the vertices in the SCC) can be reached from one or more vertices which are not part of the SCC. In the below diagram SCC 567 is connected to the SCC 234 through the crossedge 4>6. Also both SCC 234 and 567 are connected to the rest of the graph by vertex A. Both of these two SCCs have incoming forward edges from vertex A. So if user A gets the message all the users in SCC 234 and 567 will get the message too.
In order to determine if an SCC is reachable from any vertex outside of the SCC, we need to remove all the edges in the SCC and see if one or more nodes in the SCC is still connected to at least one node that is not part of the same SCC. If it is, then there is no need to include any node from this SCC to our minimal vertices list.
But if the above is not the case, then we need to include any one node from the SCC.
How can we determine if an SCC is connected to at least one node outside of the SCC ?
We find all the SCCs in the given directed graph. For each SCC: for each of the nodes present in the SCC we decrement indegree of all its adjacent nodes that are part of this SCC (to avoid including crossedges) by 1. After this operation, if the indegree of all the nodes in the current SCC are zero, then it is an isolated SCC and one user from this SCC needs to be included in our minimal list. If not, then no node from this SCC needs to be included. Try to run this logic on the above two diagrams and it will become crystal clear.
Algorithm:
From the above observations we come to the below simple yet robust algorithm to solve the problem:This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Working Solution:
import java.util.*;
/**
* Created by Abhishek on 9/21/20.
*/
public class MinimalVertices {
int discoveryTime = 0; // discovery time
// Nodes in adjacency lists are numbered from 0 to N  1
public void findSccAndDecrementIndegreeOfRoot(List< Set< Integer >> adjacencyLists, int[] indegree) {
discoveryTime = 0; // reset index to 0
int len = adjacencyLists.size();
int[] discoveryTime = new int[len];
int[] earliestDiscoveredNodeReachable = new int[len];
Deque< Integer > sccStack = new ArrayDeque<>();
boolean[] onStack = new boolean[len];
for (int i = 0; i < adjacencyLists.size(); i++) {
if (discoveryTime[i] == 0) { // indices[i] == 0 when vertex i is not already visited
dfs(adjacencyLists, discoveryTime, earliestDiscoveredNodeReachable, sccStack, onStack, i, indegree);
}
}
}
private void dfs(
List< Set< Integer >> adjacencyLists,
int[] discoveryTimes,
int[] earliestDiscoveredNodeReachable,
Deque< Integer > strongComponentStack,
boolean[] onStack,
int currentNode,
int[] indegree)
{
discoveryTime++;
discoveryTimes[currentNode] = discoveryTime; // array is zero based index, nodes are numbered from 0 to N  1
earliestDiscoveredNodeReachable[currentNode] = discoveryTime;
strongComponentStack.push(currentNode);
onStack[currentNode] = true;
for (int adjVertex : adjacencyLists.get(currentNode)) { //adjacencyList of vertex i is stored ar index i in arraylist
if (discoveryTimes[adjVertex] == 0) { // discoveryTime[v] == 0 when vertex v is not already visited
dfs(adjacencyLists, discoveryTimes, earliestDiscoveredNodeReachable, strongComponentStack, onStack, adjVertex, indegree);
earliestDiscoveredNodeReachable[currentNode] =
Math.min(earliestDiscoveredNodeReachable[currentNode], earliestDiscoveredNodeReachable[adjVertex]);
} else { // adjacentVertex is already visited
if (!onStack[adjVertex]) {
// the adjacent vertex is already visited BUT it is not in the stack
// this means the current edge is just a cross edge to an SCC
// which has already been found and processed
continue;
} else {
// adjacent vertex is in stack, so must be in the same SCC
earliestDiscoveredNodeReachable[currentNode] =
Math.min(earliestDiscoveredNodeReachable[currentNode], discoveryTimes[adjVertex]);
// NOTE: Because adjacentVertex is on the stack already, the edge (currentNode, adjacentVertex)
// is a backedge in the DFS tree and
// therefore adjacentVertex is not in the subtree of currentNode.
// Because earliestDiscoveredNodeReachable[i]
// takes into account nodes reachable only through the nodes in the subtree of currentNode and we
// must stop at adjacentVertex and use discoveryTime[adjacentVertex]
// instead of earliestDiscoveredNodeReachable[adjacentVertex]. One backedge is okay, but not more than one.
}
}
}
// now that DFS on currentNode is done lets see
// if we got any SCC before backtracking
if (earliestDiscoveredNodeReachable[currentNode] == discoveryTimes[currentNode]) {
Set< Integer > sccNodes = new HashSet<>();
int top = 0;
// construct a set of all the nodes in this SCC
do {
top = strongComponentStack.pop();
sccNodes.add(top);
onStack[top] = false;
} while (top != currentNode); // root can have self loop as well. it takes care of that too.
// Determine if there is any incoming edge from
// a node that is not part of this SCC.
// Presence of a crossedge or a forward edge from outside of the SCC
// would mean that this SCC is reachable from a vertex outside of this SCC
// and need not be included in the minimum list of users to send message.
for (int current : sccNodes) {
for (int otherNode : sccNodes) {
if (adjacencyLists.get(otherNode).contains(current)) {
indegree[current];
}
}
}
boolean isolatedSCC = true;
for (int sccNode : sccNodes) {
if (indegree[sccNode] != 0) {
isolatedSCC = false;
}
}
for (int sccNode : sccNodes) {
indegree[sccNode] = Integer.MAX_VALUE;
}
if (isolatedSCC) {
indegree[currentNode] = 0;
}
}
}
public List< Integer> getMinimalVertices(List< Set< Integer >> adjacencyLists) {
int totalNumberOfUsers = adjacencyLists.size();
int[] indegree = new int[totalNumberOfUsers];
for (Set< Integer > adjacencyList : adjacencyLists) {
for (int user : adjacencyList) {
indegree[user]++;
}
}
findSccAndDecrementIndegreeOfRoot(adjacencyLists, indegree);
List< Integer > res = new ArrayList<>();
for (int i = 0; i < totalNumberOfUsers; i++) {
if (indegree[i] == 0) {
res.add(i);
}
}
return res;
}
public static void main(String[] args) {
/*
0<1
_
\ /
_\ /
2
/ \

3

\ /
6 _
/ \
/_ \
4>5
Expected Result => 3
*/
List< Set< Integer >> adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
adjLists.add(new HashSet< Integer >() {{ add(2); add(6); }}); // for node 3
adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6
MinimalVertices ob = new MinimalVertices();
List< Integer > res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0<1
_
\ /
_\ /
2
3
6 _
/ \
/_ \
4>5
Expected Result => 3 and (0 or 1 or 2) and (4 or 5 or 6)
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
adjLists.add(new HashSet< Integer >()); // for node 3
adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0<1
_
\ /
_\ /
2
^

3
6 _
/ \
/_ \
4>5
Expected Result => 3 and (4 or 5 or 6)
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
adjLists.add(new HashSet< Integer >() {{ add(2);}}); // for node 3
adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
adjLists.add(new HashSet< Integer >() {{ add(6); }}); // for node 5
adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 6
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0<1
_
\ /
_\ /
2

\ /
3 _
/ \
/_ \
4>5
Expected result => 0 or 1 or 2
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
adjLists.add(new HashSet< Integer >() {{ add(1); add(3); }}); // for node 2
adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 3
adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
adjLists.add(new HashSet< Integer >() {{ add(3); }}); // for node 5
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0<1
_
\ /
_\ /
2
3 _
/ \
/_ \
4>5
Expected result => (0 or 1 or 2) and (3 or 4 or 5)
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >() {{ add(2); }}); // for node 0
adjLists.add(new HashSet< Integer >() {{ add(0); }}); // for node 1
adjLists.add(new HashSet< Integer >() {{ add(1); }}); // for node 2
adjLists.add(new HashSet< Integer >() {{ add(4); }}); // for node 3
adjLists.add(new HashSet< Integer >() {{ add(5); }}); // for node 4
adjLists.add(new HashSet< Integer >() {{ add(3); }}); // for node 5
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0
Expected Result: 0
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >()); // for node 0
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
0>1
^ 
_______
ExpectedResult: 0 or 1
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >(){{add(1);}}); // for node 0
adjLists.add(new HashSet< Integer >(){{add(0);}}); // for node 1
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
/*
1>0
ExpectedResult: 1
*/
adjLists = new ArrayList<>();
adjLists.add(new HashSet< Integer >()); // for node 0
adjLists.add(new HashSet< Integer >(){{add(0);}}); // for node 1
ob = new MinimalVertices();
res = ob.getMinimalVertices(adjLists);
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
}
}
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