1557. Minimum Number of Vertices to Reach All Nodes Medium

1/**
2 * [1557] Minimum Number of Vertices to Reach All Nodes
3 *
4 * Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.
5 * 
6 * Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.
7 * 
8 * Notice that you can return the vertices in any order.
9 * 
10 *  
11 * Example 1:
12 * 
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/07/untitled22.png" style="width: 231px; height: 181px;" />
14 * 
15 * 
16 * Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
17 * Output: [0,3]
18 * Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].
19 * 
20 * Example 2:
21 * 
22 * <img alt="" src="https://assets.leetcode.com/uploads/2020/07/07/untitled.png" style="width: 201px; height: 201px;" />
23 * 
24 * 
25 * Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
26 * Output: [0,2,3]
27 * Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.
28 * 
29 * 
30 *  
31 * Constraints:
32 * 
33 * 
34 * 	2 <= n <= 10^5
35 * 	1 <= edges.length <= min(10^5, n * (n - 1) / 2)
36 * 	edges[i].length == 2
37 * 	0 <= fromi, toi < n
38 * 	All pairs (fromi, toi) are distinct.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/
44// discuss: https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn find_smallest_set_of_vertices(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
50        vec![]
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_1557() {
62    }
63}
64