C# DFS with Backtracking Solution
Intuition\n-  Describe your first thoughts on how to solve this problem. Graph Traversal: Since the problem involves finding paths from node 0 back to node 0, a
# Intuition\n- <!-- Describe your first thoughts on how to solve this problem. -->Graph Traversal: Since the problem involves finding paths from node 0 back to node 0, a natural way to explore the graph is using DFS. DFS allows us to explore all possible paths while keeping track of the time taken.\n\n- Maximizing Quality: The quality of a path is determined by the sum of the values of unique nodes visited. Therefore, we need to ensure that each node is only added to the total quality once, even if it is revisited later.\n\n- Backtracking: To explore different paths, backtracking is essential. After exploring a particular path, we need to "unvisit" nodes and undo any changes made to the current quality. This allows us to try other paths that might lead to better results.\n\n- Pruning Paths: Since we are constrained by the maximum allowed time (maxTime), we prune paths that exceed the allowed time by returning early from the DFS function.\n\n- Tracking Visits: The visited array tracks how many times a node has been visited. This is important for determining whether a node\u2019s value should be added to the current quality when visiting it for the first time.\n___\n\n# Approach\n<!-- Describe your approach to solving the problem. -->//  Build the Graph: Represent the graph using an adjacency list for efficient traversal.\n//  Depth-First Search (DFS): Implement a DFS starting from node 0. Keep track of:\n//  *Time Used: Total time taken so far.\n//  *Current Quality: Sum of unique node values visited.\n//  *Visited Nodes: An array to track whether a node has been visited to prevent adding its value multiple times.\n//  Backtracking: Since nodes and edges can be revisited, we need to backtrack after exploring each path to reset the state for the next path.\n//  Prune Paths Exceeding maxTime: If the time used exceeds maxTime, we prune that path.\n//  Update Maximum Quality: Whenever we return to node 0, we check if the current quality is greater than the maximum found so far.\n___\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(V + E), where \'V\' is the number of vertices (nodes) in the graph. and \'E\' is the number of edges.\n___\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(V + E), primarily due to the space required for the recursion stack in the DFS, The visited array to track visited nodes, and the adjacency list, which takes O(V + E) space.\n___\n\n# Code\n```csharp []\npublic class Solution {\n    int maxQuality;\n    int[] values;\n    List<(int neighbor, int time)>[] adjList;\n    int[] visited;\n    int maxTime;\n    public int MaximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        this.values = values;\n        this.maxTime = maxTime;\n        int n = values.Length;\n        adjList = new List<(int, int)>[n];\n        for(int i = 0; i < n; i++) adjList[i] = new List<(int, int)>();\n        foreach(var edge in edges) {\n            int u = edge[0];\n            int v = edge[1];\n            int time = edge[2];\n            adjList[u].Add((v, time));\n            adjList[v].Add((u, time));\n        }\n        visited = new int[n];\n        int currentQuality = values[0];\n        visited[0] = 1;\n        maxQuality = values[0];\n        dfs(0, 0, currentQuality);\n        return maxQuality;\n    }\n    void dfs(int node, int timeUsed, int currentQuality) {\n        if(timeUsed > maxTime) return;\n        if(node == 0) {\n            if(currentQuality > maxQuality) maxQuality = currentQuality;\n        }\n        foreach(var (neighbor, time) in adjList[node]) {\n            int newTimeUsed = timeUsed + time;\n            if(newTimeUsed > maxTime) continue;\n            bool firstVisit = visited[neighbor] == 0;\n            if(firstVisit) currentQuality += values[neighbor];\n            visited[neighbor]++;\n            dfs(neighbor, newTimeUsed, currentQuality);\n            visited[neighbor]--;\n            if(firstVisit) currentQuality -= values[neighbor];\n        }\n    }\n}\n```
['Array', 'Backtracking', 'Graph', 'C#']