[LeetCode] 1557. Minimum Number of Vertices to Reach All Nodes

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/

Minimum Number of Vertices to Reach All Nodes - LeetCode

문제 유형 : 그래프

문제 난이도 : Medium

 

문제

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 from i to node to i.

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.

 

n개의 정점을 가지는 방향 그래프가 있다. 모든 노드에 닿을 수 있는 최소한의 정점 집합을 구해라.

 

 

풀이

간선의 목적지(간선의 1번 인덱스)를 집합에 담는다(중복 방지)

0부터 n-1까지의 숫자 중에서 집합에 없는 숫자가 조건에 맞는 숫자이다.

 

코드(C++)

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        unordered_set<int> not_roots;

        for (const auto& edge : edges) {
            not_roots.insert(edge[1]);
        }

        vector<int> result;
        for (int i = 0; i < n; ++i) {
            if (not_roots.count(i) == 0) {
                result.push_back(i);
            }
        }

        return result;
    }
};