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
The Python solution constructs an adjacency list and uses a queue for BFS traversal, ensuring we're adding necessary roles to a full potential delegation. Consequently, each BFS iteration accounts for the fuel needed by constraining nodes via BFS into a specific directional queue.