Given a directed graph G (can contain sub graphs and cycles), find the minimum number of vertices from which all nodes are reachable.
For example:
Nodes:
0, 1, 2, 3, 4, 5
Edges:
1 <- 0
0 <- 1 <- 2
3 <- 1 <- 2
2 <- 5
4 <- 5
Representation:
--> 4
/
5 --> 2 --> 1 <--> 0
\
--> 3
Matrix:
g = [[1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1],
[0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1]]Return 1 (node number 5). From node number 5 all other nodes are reachable.
If we remove edge 2 <- 5, the result is 2, because we need at least nodes number 5 and 2 to visit all nodes.
Representation of the graph if we remove the edge between nodes 2 and 5.
5 --> 4
2 --> 1 <--> 0
\
--> 3I attempted to solve this problem by finding for every node j, and array of all nodes reachable from j. Basically, I did a DFS on every node, and the result looks like this:
{
0: [True, True, False, True, False, False],
1: [True, True, False, True, False, False],
2: [True, True, True, True, False, False],
3: [False, False, False, True, False, False],
4: [False, False, False, False, True, False],
5: [True, True, True, True, True, True]
}This means that from node 0, I can reach nodes number 0, 1, 3. From node 1 I can reach nodes 0, 1 and 3. From node 5, I can reach all nodes.
Is this a good approach to solve the problem? Having this dictionary, how can I find the smallest group of nodes from which I can reach all nodes?