給出一個(gè)n個(gè)節(jié)點(diǎn)的有向無環(huán)圖，問最少可以劃分為多少個(gè)group，使得每個(gè)group內(nèi)的所有節(jié)點(diǎn)都可以從group內(nèi)其他任意一個(gè)節(jié)點(diǎn)到達(dá)
能想到的基本就是DFS或者并查集，但Discussion一個(gè)思路很巧，如果一個(gè)節(jié)點(diǎn)沒有指向它的邊，那它肯定要作為某個(gè)獨(dú)立group的一員，于是只要O(m+n)統(tǒng)計(jì)哪些節(jié)點(diǎ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