MOST INTUITIVE C++ SOLUTION !!
\n\n# Intuition\nWe Need To Reach Capital City. For This, We Need To Run A DFS Traversal From Capital City (Node 0) To All The Cities. For This, We Need To Main
**![Upvote.jpeg](https://assets.leetcode.com/users/images/c0896a1a-406f-4963-b5aa-e6ad27a8275f_1714841801.5205965.jpeg)**\n\n# Intuition\nWe Need To Reach Capital City. For This, We Need To Run A DFS Traversal From Capital City (Node 0) To All The Cities. For This, We Need To Maintain An Adjacency List And Visited Array.\n\n\nNow, We Basically Need To Count The Number Of Edges Which Are Not Leading To Capital City Directly And Indirectly.\n\nHere Is Where The Slight Modification To Adjacency List Comes To Play. Read The Approach And Comments For Better Understanding.\n\n\n\n# Approach\n1. Prepare A Boolean Array For Visited Nodes And 2D Adjacency List.\n\n2. Push Destination Node To List Of Source Node And **Negative Of Source Node** To Adjacency List Of Destination Node.\n\n3. Initialise Count Of Edges To Be Reversed = 0.\n\n4. Start DFS Traversal From Capital City (Node 0).\n\n    - **Base Case** : Current City Is Already Visited.\n    - Mark Current City Visited.\n    - Run A Loop For Adjacent Cities.\n    - Check For Visited Neighbor.\n    - In Case Of Positive Neighboring City: **Edge Needs To Be Reversed**.\n    - Increase Count.\n    - Recursive Call For DFS From Current Neighboring City.\n\n5. Return Count.\n\n# Complexity\n- Time complexity: **O (V + E)**\n\n- Space complexity: **O (V + E)**\n\n# Code\n```\n// DFS Traversal.\n\nclass Solution {\npublic:\n\n    // Whenever A City With Positive Value Is Encountered.\n    // Edge Needs To Be Reversed.\n\n    void reverseEdge(int curr, vector<vector<int>> &adj, int &count, vector<bool> &vis) {\n        \n        // Base Case.\n        if (vis[curr] == true) return;\n\n        // Mark Current City As Visited.\n        vis[curr] = true;\n\n        for (auto neighborCity : adj[curr]) {\n\n            // Reversing The Edge In Case Of Adjacent City With Positive Value.\n            // City With Positive Value Implies There Is An Edge To Current City (Not From Current City).\n\n            if (vis[abs(neighborCity)] == false) \n                if (neighborCity > 0) count++;\n            \n            // Recursive Call For The Neighboring City.\n            reverseEdge(abs(neighborCity), adj, count, vis);\n        }\n    }\n\n    int minReorder(int n, vector<vector<int>> &connections) {\n        \n        vector<vector<int>> adj (n);\n        vector<bool> vis (n, false);\n\n        for (int i = 0; i < connections.size(); ++i) {\n\n            int u = connections[i][0]; // Source City.\n            int v = connections[i][1]; // Destination City.\n\n            // Modification To Standard Approach.\n            // In Adjacency List Of Destination City, Append Negative Value Of Source City.\n\n            adj[u].push_back(v);\n            adj[v].push_back(-u);\n        }\n\n        int count = 0;\n        \n        // Start DFS Traversal From Capital City.\n        reverseEdge(0, adj, count, vis);\n\n        return count;\n    }\n};
['Depth-First Search', 'Graph', 'C++']