[C++] Concise & Easy to understand DFS Solution | With Explanation
The idea is to do a DFS traversal starting from node 0. For nodes other than 0, we check the parent who called DFS on it, and if it doesn\'t have an outgoing ed
The idea is to do a DFS traversal starting from node 0. For nodes other than 0, we check the parent who called DFS on it, and if it doesn\'t have an outgoing edge to the parent, we increment the answer. We don\'t really need to reverse any edge.  \n```\nvoid dfs(int idx,int caller,vector<vector<int>> &adjList,vector<vector<int>> &outgoing,vector<bool> &visited,int &ans){\n        visited[idx]=true;\n        if(caller!=-1){     //if the city number is not 0\n            //check if there is an outgoing edge from current node to it\'s parent node (who called dfs on this node)\n            //if there is no outgoing edge, we\'ll have to reorient this edge\n            if(find(outgoing[idx].begin(),outgoing[idx].end(),caller)==outgoing[idx].end())\n                ans++;\n        }\n        for(auto i: adjList[idx]){\n            if(!visited[i]){\n                dfs(i,idx,adjList,outgoing,visited,ans);\n            }\n        }\n }\nint minReorder(int n, vector<vector<int>>& connections) {\n        int ans=0;\n        vector<vector<int>> adjList(n);     //doesn\'t cares about direction\n        vector<vector<int>> outgoing(n);    //list of outgoing nodes from a node\n        vector<bool> visited(n,false);       \n        for(auto i: connections){\n            adjList[i[0]].push_back(i[1]);\n            adjList[i[1]].push_back(i[0]);\n            outgoing[i[0]].push_back(i[1]);\n        }\n        dfs(0,-1,adjList,outgoing,visited,ans);     //start dfs from node 0 \n        return ans;\n }\n```\nThe caller argument in the dfs function denotes the node who called dfs on the current node, i.e. it\'s parent. We intially call dfs on node 0 with caller=-1 as it doesn\'t have any parent to which it wants to reach. Upvote if you found it helpful.
['Depth-First Search', 'C']