Last Updated on 2023-05-18 by Clay
題目
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.
Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.
Notice that you can return the vertices in any order.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] 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].
Example 2:
Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] Output: [0,2,3] 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.
Constraints:
2 <= n <= 10^51 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi < n- All pairs
(fromi, toi)are distinct.
這是一個圖論問題，要求在有向無循環的圖中找到一組最少的節點集合，並且這組節點集合可以訪問到圖中的所有節點。並且，題目保證存在唯一解。
解題思路
這題題目很直觀地就存在一個解法：
- 建立一個長度為 n 的陣列，來判斷當前對應索引的節點是否有入射（in-degree），即其他節點可走訪到當前判斷的節點
- 找出不存在 in-degree 的節點。由於保證唯一解，故不存在 in-degree 的節點就是可以到達其他節點的最小節點集合。
C++ 範例程式碼
\class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
// Init
vector<bool> indegree(n, false);
vector<int> results;
// Find in-degree
for (auto& edge: edges) {
indegree[edge[1]] = true;
}
// Filter the vertices that have in-degree
for (int i=0; i<n; ++i) {
if (!indegree[i]) {
results.emplace_back(i);
}
}
return results;
}
};Python 範例程式碼
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
# Init
indegree = [False] * n
# Find in-degree
for edge in edges:
indegree[edge[1]] = True
# Filter the vertices that have in-degree
return [i for i in range(n) if not indegree[i]]