C# || How To Find The Minimum Time To Collect All Apples In A Tree Using C#

May 23, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum time to collect all apples in a tree using C#.

1. Min Time – Problem Statement

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [a_i, b_i] means that exists an edge connecting the vertices a_i and b_i. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] Output: 6 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] Output: 0

2. Min Time – Solution

The following is a solution which demonstrates how to find the cheapest flights within K stops.





		
		
			2. Min Time - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum time to collect apples
// ============================================================================
public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        var adj = new Dictionary<int, List<int>>();
        foreach (int[] edge in edges) {
            int a = edge[0];
            int b = edge[1];
            if (!adj.ContainsKey(a)) {
                adj[a] = new List<int>();
            }
            if (!adj.ContainsKey(b)) {
                adj[b] = new List<int>();
            }
            adj[a].Add(b);
            adj[b].Add(a);
        }
        return DFS(0, -1, adj, hasApple);
    }

    public int DFS(int node, int parent, Dictionary<int, List<int>> adj, IList<bool> hasApple) {
        if (!adj.ContainsKey(node)) {
            return 0;
        }

        int totalTime = 0;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int childTime = DFS(child, node, adj, hasApple);
            // childTime > 0 indicates subtree of child has apples. Since the root node of the
            // subtree does not contribute to the time, even if it has an apple, we have to check it
            // independently.
            if (childTime > 0 || hasApple[child]) {
                totalTime += childTime + 2;
            }
        }
        return totalTime;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum time to collect apples
// ============================================================================
public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        var adj = new Dictionary<int, List<int>>();
        foreach (int[] edge in edges) {
            int a = edge[0];
            int b = edge[1];
            if (!adj.ContainsKey(a)) {
                adj[a] = new List<int>();
            }
            if (!adj.ContainsKey(b)) {
                adj[b] = new List<int>();
            }
            adj[a].Add(b);
            adj[b].Add(a);
        }
        return DFS(0, -1, adj, hasApple);
    }
 
    public int DFS(int node, int parent, Dictionary<int, List<int>> adj, IList<bool> hasApple) {
        if (!adj.ContainsKey(node)) {
            return 0;
        }
 
        int totalTime = 0;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int childTime = DFS(child, node, adj, hasApple);
            // childTime > 0 indicates subtree of child has apples. Since the root node of the
            // subtree does not contribute to the time, even if it has an apple, we have to check it
            // independently.
            if (childTime > 0 || hasApple[child]) {
                totalTime += childTime + 2;
            }
        }
        return totalTime;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

8 6 0

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, depth first search, leetcode

C# || How To Find The Minimum Time To Collect All Apples In A Tree Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories