Java DFS | Just dont add cycle check that we do in regular DFS
IntuitionApproachComplexity
Time complexity:
O(V+E)
Space complexity:
Code
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(V+E)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n\n    int maxQ= 0;\n\n    public void dfs(HashMap<Integer, List<int[]>> adj, int maxTime, Set<Integer> qualities, int quality, int time, int thzNode, int[] values){\n        if(time > maxTime) return;\n        if(thzNode == 0) maxQ = Math.max(maxQ, quality);\n        if(adj.get(thzNode) == null) return;\n        //DFS but just dont check for if already visisted\n        for(int[] eachConnect : adj.get(thzNode)){\n            int addedQ = quality;\n            boolean added = false;\n            if(!qualities.contains(eachConnect[0])){ //Dont take same Node twice for Quality\n                added =true;\n                qualities.add(eachConnect[0]);\n                addedQ += values[eachConnect[0]];\n            }\n            dfs(adj, maxTime, qualities, addedQ,time + eachConnect[1], eachConnect[0], values);\n            if(added) qualities.remove(eachConnect[0]);\n        }\n    }\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        HashMap<Integer, List<int[]>> adj = new HashMap();\n        for(int[] edge : edges){\n            List<int[]> exist1 = adj.getOrDefault(edge[0], new ArrayList<int[]>());\n            List<int[]> exist2 = adj.getOrDefault(edge[1], new ArrayList<int[]>());\n            //Adj list has  List< [connectedNode, PathVal] .. >\n            exist1.add(new int[]{edge[1], edge[2]});\n            exist2.add(new int[]{edge[0], edge[2]});\n            adj.put(edge[0], exist1);\n            adj.put(edge[1], exist2);\n        }\n        Set<Integer> qualities = new HashSet();\n        qualities.add(0);\n        dfs(adj, maxTime, qualities,values[0], 0, 0, values);\n        return maxQ;\n    }\n}\n```
['Java']