Minimum Number of Vertices to Reach All Nodes
给一个DAG, 求最小的set, 里面的点组成的路径可以到达所有点. 这题必有答案, 而且答案唯一
因为最后一句话, 所以直接找入度为0的点即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) { vector<int> res; unordered_set<int> set; for(auto v : edges) { set.emplace(v[1]); } for(int i = 0; i < n; i++){ if(set.find(i) == set.end()) res.push_back(i); } return res; } }; |