https://leetcode.com/discuss/interview-question/124861/digraph-cover-all-vertices-with-the-least-number-of-vertices
It's the number of strongly-connected components that aren't reachable from any outside vertex.
What if you found all vertices with no incoming edges and started BFS from those vertices? If you run out of vertices with no incoming edges, then that means the rest of the vertices are either in a cycle or completely separated.
https://github.com/allaboutjst/airbnb/blob/master/README.md
https://rextester.com/discussion/NJE76317/Minimum-Vertices-to-Traverse-Directed-Graph
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?
It's the number of strongly-connected components that aren't reachable from any outside vertex.
What if you found all vertices with no incoming edges and started BFS from those vertices? If you run out of vertices with no incoming edges, then that means the rest of the vertices are either in a cycle or completely separated.
https://github.com/allaboutjst/airbnb/blob/master/README.md
Given a directed grapjh, represented in a two dimension array, output a list of points that can be used to travese every points with the least number of visited vertices.
private void search(Set<Integer> res, Map<Integer, Set<Integer>> nodes, int cur, int start,
Set<Integer> visited, Set<Integer> currVisited) {
currVisited.add(cur);
visited.add(cur);
for (int next : nodes.get(cur)) {
if (res.contains(next) && next != start) {
res.remove(next);
}
if (!currVisited.contains(next)) {
search(res, nodes, next, start, visited, currVisited);
}
}
}
public List<Integer> getMin(int[][] edges, int n) {
Map<Integer, Set<Integer>> nodes = new HashMap<>();
for (int i = 0; i < n; i++) {
nodes.put(i, new HashSet<>());
}
for (int[] edge : edges) {
nodes.get(edge[0]).add(edge[1]);
}
Set<Integer> visited = new HashSet<>();
Set<Integer> res = new HashSet<>();
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) {
res.add(i);
visited.add(i);
search(res, nodes, i, i, visited, new HashSet<>());
}
}
return new ArrayList<>(res);
}
