Airbnb | Cover all vertices with the least number of vertices

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
        \
          --> 3

I 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?

Comments (12)