1466. Reorder Routes to Make All Paths Lead to the City Zero

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/leetcode.com

DFS

First Tab

class Solution:
    def __init__(self):
        self.res = 0
        self.visited = set()
        
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        fromWhere = {_:[] for _ in range(n)}
        goWhere = {_:[] for _ in range(n)}
        for i, j in connections:
            fromWhere[j].append(i)
            goWhere[i].append(j)
        
        def correct(city):
            self.visited.add(city)
            for c in fromWhere[city]:
                if c not in self.visited:
                    correct(c)
            for c in goWhere[city]:
                if c not in self.visited:
                    self.res += 1
                    correct(c)
        
        correct(0)
        return self.res

Improve

class Solution:
    def __init__(self):
        self.res = 0
        self.visited = set()
        
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 整理所有路径
        path = {_:[] for _ in range(n)}
        for i, j in connections:
            path[i].append((i,j))
            path[j].append((i,j))
            
        # 递归地遍历所有node，遇到逆向的就+1，然后继续往下搜
        def correct(city):
            self.visited.add(city)
            for (i, j) in path[city]:
                if j == city and i not in self.visited:
                    correct(i)
                if i == city and j not in self.visited:
                    self.res += 1
                    correct(j)
    
        correct(0)
        return self.res