给出一颗连通的有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