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个节点的树,求问若将原先树中每条无向边[a,b]当作有向边,至少需要改变其中几条边的方向才能使得每个节点都可以到达节点0
建图的时候每条路建双向边,但增加一个标记来区分方向,从节点0开始DFS一遍,记录反向边的个数即可


 1 #1466
 2 #Runtime: 1109 ms (Beats 60%)
 3 #Memory: 78.5 MB (Beats 26.15%)
 4 
 5 class Solution(object):
 6     def minReorder(self, n, connections):
 7         """
 8         :type n: int
 9         :type connections: List[List[int]]
10         :rtype: int
11         """
12         edge = defaultdict(list)
13         for x, y in connections:
14             edge[x].append((y, 1))
15             edge[y].append((x, 0))
16         vis = [0] * n
17         self.ans = 0
18         def DFS(node):
19             vis[node] = 1
20             for y, d in edge[node]:
21                 if not vis[y]:
22                     if d:
23                         self.ans += 1
24                     DFS(y)
25         DFS(0)
26         return self.ans

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