Sponsored
Sponsored
Using Depth-First Search (DFS), we can traverse the tree from the capital city '0' and calculate the minimum fuel cost required to gather all representatives in the capital city. We need to propagate the number of representatives from child nodes towards the root (capital) while managing the representatives getting into available seats effectively.
Time Complexity: O(n), where n is the number of cities as we visit each edge once.
Space Complexity: O(n), due to the storage used for the adjacency list and recursion stack.
This C solution uses a depth-first search to calculate the minimum number of liters needed. It creates an adjacency list from the input nodes and applies DFS to compute two things: the total number of people at each node (along with its subtree) and the fuel cost for moving them to the capital.
By utilizing Breadth-First Search (BFS), we can tackle this problem iteratively, processing nodes level by level from the capital outward. Track the representatives as they move towards the capital and the fuel cost incrementally.
Time Complexity: O(n) based on visiting each node.
Space Complexity: O(n) for queue storage.
1function minimumFuelCost(roads, seats) {
2 const adjList = new Map();
3 for (const [a, b] of roads) {
4 if (!adjList.has(a)) adjList.set(a, []);
5 if (!adjList.has(b)) adjList.set(b, []);
6 adjList.get(a).push(b);
7 adjList.get(b).push(a);
8 }
9
10 const visited = new Set(), queue = [[0, 0]];
11 visited.add(0);
12 let cost = 0;
13
14 while (queue.length) {
15 const [node, reps] = queue.shift();
16 const max_reps = reps + 1;
17 const nodeFuel = Math.ceil(max_reps / seats);
18 cost += nodeFuel;
19
20 for (let neighbor of (adjList.get(node) || [])) {
21 if (!visited.has(neighbor)) {
22 visited.add(neighbor);
23 queue.push([neighbor, max_reps]);
24 }
25 }
26 }
27
28 return cost;
29}
30
31const roads = [[0,1], [0,2], [0,3]];
32const seats = 5;
33console.log(minimumFuelCost(roads, seats));This JavaScript example uses BFS to process nodes iteratively, evaluating and tallying fuel expenditures. The queue records cities for traversal, continuously updating the total cost as representatives move upwards to the capital.