原题链接：Leetcode 1466. 重新规划路线

BFS

class Solution {
public:
    vector<vector<int>> adj;
    vector<vector<int>> in;
    vector<int> visit;
    int minReorder(int n, vector<vector<int>>& connections) {
        adj.resize(n);
        visit.resize(n);
        in.resize(n);
        for(auto x:connections)
        {
            int a=x[0],b=x[1];
            adj[a].push_back(b);
            in[b].push_back(a);
        }
        int res=0;
        queue<int> q; 
        q.push(0);
        visit[0]=1;
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            for(auto x:adj[now])
            {
                if(!visit[x])
                {
                    res++;
                    visit[x]=1;
                    q.push(x);
                }
            }
            for(auto x:in[now])
            {
                if(!visit[x])
                {
                    visit[x]=1;
                    q.push(x);
                }
            }
        }
        return res;
    }
};

DFS

class Solution {
public:
    vector<vector<int>> adj;
    vector<vector<int>> in;
    vector<int> visit;
    int res=0;
    void dfs(int now)
    {
        visit[now]=1;
        for(auto x:adj[now])
        {
            if(!visit[x])
            {
                res++;
                dfs(x);
            }
        } 
        for(auto x:in[now])
        {
            if(!visit[x]) dfs(x);
        }
    }
    int minReorder(int n, vector<vector<int>>& connections) {
        adj.resize(n);
        visit.resize(n);
        in.resize(n);
        for(auto x:connections)
        {
            int a=x[0],b=x[1];
            adj[a].push_back(b);
            in[b].push_back(a);
        }
        dfs(0);
        return res;
    }
};