Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1466. Reorder Routes to Make All Paths Lead to the City Zero

---

參考資訊：
https://algo.monster/liteproblems/1466
https://blog.csdn.net/fuxuemingzhu/article/details/106597991

題目：


解答：

class Solution {
public:
    int dfs(int city, const unordered_map<int, unordered_map<int, int>>& cost, vector<int>& visited, int *r) {
        visited[city] = 1;

        for (const auto& item : cost.at(city)) {
            int t = item.first;
            int c = item.second;

            if (visited[t] == 0) {
                (*r) += c;
                dfs(t, cost, visited, r);
            }
        }
        return 0;
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        int r = 0;
        vector<int> visited(n, 0);
        unordered_map<int, unordered_map<int, int>> cost;

        for (vector<int> n : connections) {
            int s0 = n[0];
            int s1 = n[1];

            cost[s0][s1] = 1;
            cost[s1][s0] = 0;
        }

        dfs(0, cost, visited, &r);
        return r;
    }
};