Day 83 || DFS || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Create an adjacency list \'adj\' to represent the connections between cities. For each connection in the input list \'connections\', add two entries in \'adj\' - one for the city away from 0 and another for the city towards 0.\n2. Define a DFS function \'dfs\' that takes \'adj\', \'visited\', \'minChange\', and \'currCity\' as inputs.\n3. Mark the current city as visited.\n4. Iterate through all the neighbour cities of the current city in the adjacency list.\n5. If a neighbour city is not visited, check the direction of the connection (1 or -1).\n6. If the direction is 1, increment the \'minChange\' counter.\n7. Call the DFS function recursively with the neighbour city as the current city.\n8. In the main function, initialize a boolean vector \'visited\' of size \'n\' to keep track of visited cities, and set \'minChange\' to 0.\n9. Call the DFS function with inputs \'adj\', \'visited\', \'minChange\', and 0 (starting city).\n10. Return the value of \'minChange\'.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\nclass Solution {\npublic:\n    void dfs(vector<vector<pair<int, int>>>& adj, vector<bool>& visited, int& minChange, int currCity) {\n        visited[currCity] = true;\n        for (auto neighbourCity : adj[currCity]) {\n            if (!visited[neighbourCity.first]) {\n                if (neighbourCity.second == 1)\n                    minChange++;\n                dfs(adj, visited, minChange, neighbourCity.first);\n            }\n        }\n    }\n    int minReorder(int n, vector<vector<int>>& connections) {\n        vector<vector<pair<int, int>>> adj(n);\n        for (auto connection : connections) {\n            adj[connection[0]].push_back({connection[1], 1}); // city away from 0\n            adj[connection[1]].push_back({connection[0], -1}); // city toward 0\n        }\n        vector<bool> visited(n, false);\n        int minChange = 0;\n        dfs(adj, visited, minChange, 0);\n        return minChange;\n    }\n};\n```\n```Java []\nclass Solution {\n    public void dfs(List<List<Pair<Integer, Integer>>> adj, boolean[] visited, int[] minChange, int currCity) {\n        visited[currCity] = true;\n        for (Pair<Integer, Integer> neighbourCity : adj.get(currCity)) {\n            if (!visited[neighbourCity.getKey()]) {\n                if (neighbourCity.getValue() == 1) {\n                    minChange[0]++;\n                }\n                dfs(adj, visited, minChange, neighbourCity.getKey());\n            }\n        }\n    }\n    \n    public int minReorder(int n, int[][] connections) {\n        List<List<Pair<Integer, Integer>>> adj = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adj.add(new ArrayList<>());\n        }\n        for (int[] connection : connections) {\n            adj.get(connection[0]).add(new Pair<>(connection[1], 1));\n            adj.get(connection[1]).add(new Pair<>(connection[0], -1));\n        }\n        boolean[] visited = new boolean[n];\n        int[] minChange = new int[1];\n        dfs(adj, visited, minChange, 0);\n        return minChange[0];\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def dfs(self, adj: List[List[Tuple[int, int]]], visited: List[bool], minChange: List[int], currCity: int) -> None:\n        visited[currCity] = True\n        for neighbourCity in adj[currCity]:\n            if not visited[neighbourCity[0]]:\n                if neighbourCity[1] == 1:\n                    minChange[0] += 1\n                self.dfs(adj, visited, minChange, neighbourCity[0])\n    \n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        adj = [[] for _ in range(n)]\n        for connection in connections:\n            adj[connection[0]].append((connection[1], 1))\n            adj[connection[1]].append((connection[0], -1))\n        visited = [False] * n\n        minChange = [0]\n        self.dfs(adj, visited, minChange, 0)\n        return minChange[0]\n\n```\n\n# Time Complexity and Space Complexity:\n- **Time complexity :**\n\nThe adjacency list representation of the graph is constructed in O(E) time as we iterate through the given connections vector and add the edges to the corresponding vertices\' adjacency lists.\n\nThe depth-first search traversal is performed on each connected component of the graph, which is O(V) in the worst case when the graph is a complete graph. Within each connected component, each vertex is visited at most twice, once for marking it as visited and once for traversing its neighbors. Thus, the overall time complexity of the depth-first search traversal is O(V + E).\n\nTherefore, **the total time complexity of the solution is O(E + V + V + E) = O(2E + 2V) = O(E + V).**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity :**\n\nThe adjacency list representation of the graph is stored in memory, which takes O(E + V) space, where each vertex is stored once, and each edge is stored once in the adjacency list of its endpoints.\n\nThe visited array used to mark vertices as visited or not visited also takes O(V) space.\n\nIn the worst case, when the depth-first search traversal visits all vertices, the recursion stack could contain all the vertices in the connected component, which would take O(V) space.\n\nTherefore, **the total space complexity of the solution is O(E + V + V) = O(E + 2V) = O(E + V).**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Depth-First Search', 'Graph', 'C++', 'Java', 'Python3']