[Java] Straight Forward DFS (Generic Solution) with Detail Explanation
The idea which I have tried to implement through code is as follows. \nThe code will automatically handle the directions. Don\'t worry much about them yet.\nThe
The idea which I have tried to implement through code is as follows. \nThe code will automatically handle the directions. Don\'t worry much about them yet.\nThere is no cycle in the graph.\nOnce you start traversing from 0, you start doing a dfs, all the nodes which you have visited traversing the edges were the wrong esdges which you will be inverting later on, so why not just count them.\nFor those nodes which have not been visited yet, again start with a DFS.\nFor instance in the first test case of the problem after doing dfs with node 0, you have visited node 0, node 1 and node 3. Now you again start DFS from the node 2(next unvisited node) but when you reach 3, you realise that 3 has already been visited implying that you have taken care of having a route from 3 to 0 somehow. Moreover you reached 3 from 2 so indirectly there is a path now from 2 to 0 as well. So no need to worry about 2. Now in future if there is a node say x whose dfs when done you reach 2, you will not have worry about x as well since then there would be a path from x to 0 indirectly.\nNow talking about node 4 and node 5, you start DFS from the next unvisited node that is 4. You can reach node 0 and node 5 but node 0 was visited so nothing will get added to the total edges due to that but since 5 was unvisited we will have to invert the edge connecting node 4 and node 5, in other words we add the contribution of the edge connecting node 4 and node 5 to our total no. of edges we need to invert.\n\nUpvote if you like the idea!!\n```\nclass Solution {\n    public static int dfs(List<List<Integer>> g, int curr, boolean[] visited) {\n        visited[curr] = true;\n        List<Integer> adj = g.get(curr);\n        int ans = 0;\n        for(int i = 0; i < adj.size(); i++) if(!visited[adj.get(i)]) ans += 1 + dfs(g, adj.get(i), visited);\n        return ans;\n    }\n    public int minReorder(int n, int[][] connections) {\n        List<List<Integer>> g = new ArrayList<>();\n        for(int i = 0; i < n; i++) g.add(new ArrayList<>());\n        int m = connections.length;\n        for(int i = 0; i < m; i++) {\n            int sv = connections[i][0], ev = connections[i][1];\n            g.get(sv).add(ev);\n        }\n        boolean[] visited = new boolean[n];\n        int ans = 0;\n        for(int i = 0; i < n; i++) if(!visited[i]) ans += dfs(g, i, visited);\n        return ans;\n    }\n}
[]