class Solution {
public:
int minReorder(int n, vector<vector<int>>& connections) {
vector<vector<int>> graph(n);
for (const vector<int>& conn : connections) {
graph[conn[0]].push_back(conn[1]);
graph[conn[1]].push_back(-conn[0]); // - := conn[0] -> conn[1]
}
return dfs(graph, 0, -1);
}
private:
int dfs(const vector<vector<int>>& graph, int u, int parent) {
int change = 0;
for (const int v : graph[u]) {
if (abs(v) == parent)
continue;
if (v > 0)
++change;
change += dfs(graph, abs(v), u);
}
return change;
}
};