給出一顆連通的有n個節(jié)點的樹，求問若將原先樹中每條無向邊[a,b]當(dāng)作有向邊，至少需要改變其中幾條邊的方向才能使得每個節(jié)點都可以到達(dá)節(jié)點0
建圖的時候每條路建雙向邊，但增加一個標(biāo)記來區(qū)分方向，從節(jié)點0開始DFS一遍，記錄反向邊的個數(shù)即可
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