Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个n个节点的有向无环图,问最少可以划分为多少个group,使得每个group内的所有节点都可以从group内其他任意一个节点到达
能想到的基本就是DFS或者并查集,但Discussion一个思路很巧,如果一个节点没有指向它的边,那它肯定要作为某个独立group的一员,于是只要O(m+n)统计哪些节点没有指向它的边即可

 1 #1557
 2 #Runtime: 976 ms (Beats 46.57%)
 3 #Memory: 54.4 MB (Beats 87.67%)
 4 
 5 class Solution(object):
 6     def findSmallestSetOfVertices(self, n, edges):
 7         """
 8         :type n: int
 9         :type edges: List[List[int]]
10         :rtype: List[int]
11         """
12         has_input = [False] * n
13         ans = []
14         for edge in edges:
15             has_input[edge[1]] = True
16         for i, r in enumerate(has_input):
17             if not r:
18                 ans.append(i)
19         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理