Java | DFS Solution With Explanation | Cost of Moving Forward In Case of Bidirectional Roads
Problem Intuition-\nClearly, We need roads that take us to zero.\nIf Start a dfs from the zero, It will follow forward edges. The forward edges will take us far
**Problem Intuition-**\nClearly, We need roads that take us to zero.\nIf Start a dfs from the zero, It will follow forward edges. The forward edges will take us far from zero, So you need to reverse those edges.\n\n\n**Code Explanation-**\nConsider the graph to be birectional, (rather make it directional) , such that the the cost of forward edges( original edges) is 1 and the cost of reversed edges is 0. \nStore them in the adjacency list such that adj[0] -> [1,1] means that there is a forward edge from 0 to 1.\nStart dfs from 0. Count whenever you traverse thorugh a forward edge. Return count.\n\n*Note- The edges are given in the forward manner (out degrees) only. Thats why we are considering cost of original edges as 1.*\n\n*Please feel free to ask any doubts. Also please upvote if you find it helpful.*\n\n\n```\nclass Solution {\n    int count = 0 ;\n    \n    public int minReorder(int n, int[][] connections) {\n        ArrayList<ArrayList< int[]> > adj = new ArrayList<ArrayList<int[]> >() ;\n        \n        for(int i = 0 ; i < n ; i++){\n            adj.add(new ArrayList<int[]>() );\n        }\n        \n        for(int i = 0 ; i < connections.length ; i++){\n            int u = connections[i][0] ;\n            int v = connections[i][1] ;\n            \n            adj.get(u).add(new int[]{v , 1} );\n            adj.get(v).add(new int[]{u , 0}) ;\n        }\n        \n        int[] visited = new int[n] ;\n        Arrays.fill(visited , -1) ;\n        \n        \n        dfs(0 , adj , visited) ;\n        \n        \n        return  count ;\n    }\n    \n    private void dfs(int src , ArrayList<ArrayList<int[]>> adj , int[] visited){\n        visited[src] = 1 ;\n        \n        for(int[] arr : adj.get(src) ){\n            \n            int num = arr[0] ;\n            \n            if(visited[num] == -1){\n                count += arr[1]  ;\n                dfs(num , adj , visited) ;\n            }\n        }\n        \n        \n        \n        return ;\n    }\n}\n```
['Depth-First Search', 'Java']