这道题要求的是，在一个有向图中，能够到达所有定点的出发点的标号。
理解题意，就是求入度为0的所有定点。
理解题意后，这道题就变的非常简单了。输入的数据是数组表示的边。两遍扫描，第一遍扫描所有的边，把到达的点标记出来。第二遍扫描所有的点，看看哪个定点入度为0.
- C++
class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
vector<bool> in(n);
for (const auto edge: edges) in[edge[1]] = true;
vector<int> res;
for (int i = 0; i < n; ++i)
if (!in[i]) res.push_back(i);
return res;
}
};
- Java
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
boolean[] in = new boolean[n];
for (List<Integer> edge: edges) in[edge.get(1).intValue()] = true;
List<Integer> res = new ArrayList<Integer> ();
for (int i = 0; i < n; ++i)
if (!in[i]) res.add(i);
return res;
}
}
- Python3
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
innode = [False] * n
for edge in edges:
innode[edge[1]] = True
res = []
for i in range(n):
if not innode[i]:
res.append(i)
return res
#直达链接
LeetCode 1557. Minimum Number of Vertices to Reach All Nodes