1466. 重新规划路线

1466. 重新规划路线

• 难度: medium
• 原始链接: https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero
• 标签: dfs

解法一: dfs

go

func minReorder(n int, connections [][]int) int {
    roads := make([][]int, n)
    for _, connection := range connections {
        roads[connection[0]] = append(roads[connection[0]], -connection[1])
        roads[connection[1]] = append(roads[connection[1]], connection[0])
    }
    ans := 0
    var dfs func (start, parent int)
    dfs = func (start, parent int) {
        for _, road := range roads[start] {
            if abs(road) == parent {
                continue
            }
            if road < 0 {
                ans++
                road = -road
            }
            dfs(road, start)
        }
    }
    dfs(0, 0)
    return ans
}

func abs(num int) int {
    if num >= 0 {
        return num
    }
    return -num
}

java

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] roads = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            roads[i] = new ArrayList<>();
        }
        for (int[] connection : connections) {
            roads[connection[0]].add(new int[]{connection[1], 1});
            roads[connection[1]].add(new int[]{connection[0], 0});
        }
        return this.dfs(0, -1, roads);
    }

    private int dfs(int start, int parent, List<int[]>[] roads) {
        int ans = 0;
        for (int[] road : roads[start]) {
            if (road[0] == parent) {
                continue;
            }
            ans += road[1] + this.dfs(road[0], start, roads);
        }
        return ans;
    }

}