给出一个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