Simulation volume leetcode [general] 1557 The minimum number of points that can reach all points

1557. The minimum number of points that can reach all points

To give you one Directed acyclic graph  , n  Node number is 0  To n-1 , And an array of edges edges , among edges[i] = [fromi, toi]  Represents a slave point   fromi  point-to-point  toi  The directed side of .

Find the smallest set of points so that all points in the graph can be reached from these points . The problem guarantees that the solution exists and is unique .

You can return these node numbers in any order .

Example 1：

Input ：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output ：[0,3]
explain ： All nodes cannot be reached from a single node . from 0 We can get to [0,1,2,5] . from 3 We can get to [3,4,2,5] . So we output [0,3] .
Example 2：

Input ：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output ：[0,2,3]
explain ： Note the node 0,3 and 2 Unable to reach... From other nodes , So we have to include them in the result point set , These points can reach the node 1 and 4 .

Tips ：

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
All point pairs  (fromi, toi)  Different from each other .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-number-of-vertices-to-reach-all-nodes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        """  Overtime case：https://leetcode-cn.com/submissions/detail/240988246/testcase/ """
        pass

    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        res = set(range(n))
        for start,end in edges:
            if end in res: res.remove(end)
        return list(res)

    def findSmallestSetOfVertices_ Overtime (self, n: int, edges: List[List[int]]) -> List[int]:
        res = [x for x in range(n)]
        for start,end in edges:
            if end in res: res.remove(end)
        return res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.findSmallestSetOfVertices(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [6,[[0,1],[0,2],[2,5],[3,4],[4,2]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！