dev/democards/problems/problems/1557.minimum-number-of-vertices-to-reach-all-nodes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Given a **  directed acyclic graph**, with `n` vertices numbered from `0` to\n",
    "`n-1`, and an array `edges` where `edges[i] = [fromi, toi]` represents a\n",
    "directed edge from node `fromi` to node `toi`.\n",
    "\n",
    "Find _the smallest set of vertices from which all nodes in the graph are\n",
    "reachable_. It's guaranteed that a unique solution exists.\n",
    "\n",
    "Notice that you can return the vertices in any order.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2020/07/07/untitled22.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]\n",
    "    Output: [0,3]\n",
    "    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].\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2020/07/07/untitled.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]\n",
    "    Output: [0,2,3]\n",
    "    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.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "  * `2 <= n <= 10^5`\n",
    "  * `1 <= edges.length <= min(10^5, n * (n - 1) / 2)`\n",
    "  * `edges[i].length == 2`\n",
    "  * `0 <= fromi, toi < n`\n",
    "  * All pairs `(fromi, toi)` are distinct."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "find_smallest_set_of_vertices (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function find_smallest_set_of_vertices(n::Int, edges::Vector{Vector{Int}})::Vector{Int}\n",
    "    set = Set(edge[2] for edge in edges)\n",
    "    res = Int[]\n",
    "    for i in 0:n-1\n",
    "        (i in set) || push!(res, i)\n",
    "    end\n",
    "    res\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}