1557-kir3i.md

1557. Minimum Number of Vertices to Reach All Nodes

Solution

• 시간복잡도: O(N+E)

• 알고리즘

  그래프

• 풀이설명

  1. 주어진 edge를 순회하며 각 노드의 indgree를 기록합니다.
  2. indegree가 0인 노드는 다른 노드로부터 방문할 수 없는 노드이므로 정답 set에 포함해야 합니다. 반대로 indegree가 1 이상인 노드는 다른 노드로부터 방문할 수 있는 노드이므로 정답 set에 포함하지 않습니다.

• 소스코드

  • C++

    class Solution {
    public:
        vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
            vector<int> ind(n, 0);
            for(const auto &e: edges)
                ind[e[1]]++;
            vector<int> ans;
            for(int i=0; i<n; i++)
                if(ind[i] == 0)
                    ans.push_back(i);
            return ans;
        }
    };

  • Python

    class Solution:
        def findSmallestSetOfVertices(self, n, edges):
            ind = [0] * n
            for e in edges:
                ind[e[1]] += 1
            
            return [i for i, d in enumerate(ind) if d == 0]

  • Java

    class Solution {
        public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
            int[] ind = new int[n];
            for(List<Integer> e: edges)
                ind[e.get(1)]++;
            
            List<Integer> ans = new ArrayList();
            for(int i=0; i<n; i++)
                if(ind[i] == 0)
                    ans.add(i);
            return ans;
        }
    }