javascript 解法, 执行用时: 356 ms, 内存消耗: 73.9 MB, 提交时间: 2023-12-07 00:21:31

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var minReorder = function(n, connections) {
    const e = new Array(n).fill(0).map(() => new Array());
    for (const edge of connections) {
        e[edge[0]].push([edge[1], 1]);
        e[edge[1]].push([edge[0], 0]);
    }

    const dfs = function(x, parent) {
        let res = 0;
        for (const edge of e[x]) {
            if (edge[0] == parent) {
                continue;
            }
            res += edge[1] + dfs(edge[0], x);
        }
        return res;
    }
    return dfs(0, -1, e);
};

golang 解法, 执行用时: 172 ms, 内存消耗: 18.8 MB, 提交时间: 2023-12-07 00:21:01

func dfs(x, parent int, e [][][]int) int {
    res := 0
    for _, edge := range e[x] {
        if edge[0] == parent {
            continue
        }
        res += edge[1] + dfs(edge[0], x, e)
    }
    return res
}

func minReorder(n int, connections [][]int) int {
    e := make([][][]int, n)
    for _, edge := range connections {
        e[edge[0]] = append(e[edge[0]], []int{edge[1], 1})
        e[edge[1]] = append(e[edge[1]], []int{edge[0], 0})
    }
    return dfs(0, -1, e)
}

java 解法, 执行用时: 31 ms, 内存消耗: 70 MB, 提交时间: 2023-12-07 00:20:35

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

    public int dfs(int x, int parent, List<int[]>[] e) {
        int res = 0;
        for (int[] edge : e[x]) {
            if (edge[0] == parent) {
                continue;
            }
            res += edge[1] + dfs(edge[0], x, e);
        }
        return res;
    }
}

cpp 解法, 执行用时: 296 ms, 内存消耗: 115.2 MB, 提交时间: 2023-12-07 00:20:11

class Solution {
public:
    int dfs(int x, int parent, vector<vector<pair<int, int>>>& e) {
        int res = 0;
        for (auto &edge : e[x]) {
            if (edge.first == parent) {
                continue;
            }
            res += edge.second + dfs(edge.first, x, e);
        }
        return res;
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> e(n);
        for (auto edge : connections) {
            e[edge[0]].push_back(make_pair(edge[1], 1));
            e[edge[1]].push_back(make_pair(edge[0], 0));
        }
        return dfs(0, -1, e);
    }
};

python3 解法, 执行用时: 1524 ms, 内存消耗: 35 MB, 提交时间: 2022-08-01 11:03:22

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        edge = [[] for _ in range(n)]
        for p, c in connections:
            edge[p].append((c, 1))
            edge[c].append((p, 0))
        quee = [0]
        vist = [False] * n
        vist[0] = True
        ans = 0
        while quee:
            i = quee.pop(0)
            for n, c in edge[i]:
                if not vist[n]:
                    vist[n] = True
                    ans += c
                    quee.append(n)
        return ans