LeetCode 1557. Minimum Number of Vertices to Reach All Nodes

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCode 1557Minumum Number of Vertices to Reach All Nodesを解きました。

設問

与えられた有向非巡回グラフに対して、全てのノードにたどり着くための最小のノードの集合を返す問題。

解

引数としてエッジの集合が与えられます。エッジの指し先はすべて辿れるものとしてvisitedをマークしていきます。visitedがつかないノードはどのノードからも指されていないことになるので、これを全て選べば全ノードにたどり着くことができます。

計算量はO(N)で、消費メモリはO(N)になります。

class Solution {
   public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<bool> visited(n, false);
        vector<int> ans;

        for (auto& e : edges) {
            visited[e[1]] = true;
        }

        for (size_t i = 0; i < n; i++) {
            if (visited[i]) ans.push_back(i);
        }

        return ans;
    }
};