Sponsored
Sponsored
The nodes that have no incoming edges cannot be reached by any other nodes. Thus, these nodes must be included in the result set for ensuring all nodes in the graph are reachable. This is because they can naturally be start points of paths that reach out to other nodes.
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.
1using System.Collections.Generic;
2
3public IList<int> FindSmallestSetOfVertices(int n, IList<IList<int>> edges) {
4 bool[] hasIncoming = new bool[n];
5 foreach (var edge in edges) {
6 hasIncoming[edge[1]] = true;
7 }
8 var result = new List<int>();
9 for (int i = 0; i < n; i++) {
10 if (!hasIncoming[i]) {
11 result.Add(i);
12 }
13 }
14 return result;
15}
16This approach employs a boolean array to monitor nodes with incoming edges. After processing all edges, we gather nodes with no incoming edges to ensure all others can be reached.