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.
1function minimumFuelCost(roads, seats) {
2 const adjList = new Map();
3 const visited = new Set();
4
5 function dfs(node) {
6 visited.add(node);
7 let representatives = 1;
8 for (let neighbor of (adjList.get(node) || [])) {
9 if (!visited.has(neighbor)) {
10 const reps = dfs(neighbor);
11 cost += Math.ceil(reps / seats);
12 representatives += reps;
13 }
14 }
15 return representatives;
16 }
17
18 for (const [a, b] of roads) {
19 if (!adjList.has(a)) adjList.set(a, []);
20 if (!adjList.has(b)) adjList.set(b, []);
21 adjList.get(a).push(b);
22 adjList.get(b).push(a);
23 }
24
25 let cost = 0;
26 dfs(0);
27 return cost;
28}
29
30const roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]];
31const seats = 2;
32console.log(minimumFuelCost(roads, seats));
This JavaScript solution maps the roads into an adjacency list to facilitate tree representation and applies DFS for fuel cost computation. The recursive DFS travels from node 0 accumulatively processing representatives constrained by car seats.
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.
1
This Java code uses BFS to calculate the minimum fuel cost iteratively. A queue tracks progression through city nodes, maintaining records of representatives as they move, accurately calculating fuel sacrifices needed where cars contribute surplus passengers.