5426. 重新规划路线

5426. 重新规划路线

没见过的dfs题型，以及做法
想清楚dir的作用
从上往下就是+1，从下往上就是0。
push_back为1的是从a到b的出边，也就是从g[u]到ver是出边 ，方向是反的。

class Solution {
public:
    vector<vector<pair<int,int>>> g;
    int minReorder(int n, vector<vector<int>>& cs) {
        g=vector<vector<pair<int,int>>>(n);
        for(auto i:cs){
            int a=i[0],b=i[1];
            g[a].push_back({b,1}); // a->b 
            g[b].push_back({a,0});
        }
        return dfs(0,-1);
    }
    
    int dfs(int u,int father){
        int res=0;
        for(auto e:g[u]){
            int ver=e.first,dir=e.second;
            if(ver==father)continue;
            res+=dfs(ver,u)+dir;
        }
        return res;
    }
};