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.
1import java.util.*;
2
3public class Solution {
4 static ArrayList<Integer>[] adjList;
5 static boolean[] visited;
6
7 private static int dfs(int node, int seats, long[] cost) {
8 visited[node] = true;
9 int representatives = 1;
10 for (int neighbor : adjList[node]) {
11 if (!visited[neighbor]) {
12 int reps = dfs(neighbor, seats, cost);
13 cost[0] += (reps + seats - 1) / seats;
14 representatives += reps;
15 }
16 }
17 return representatives;
18 }
19
20 public static long minimumFuelCost(int[][] roads, int seats) {
21 int n = roads.length + 1;
22 adjList = new ArrayList[n];
23 visited = new boolean[n];
24 for (int i = 0; i < n; i++) {
25 adjList[i] = new ArrayList<>();
26 }
27 for (int[] road : roads) {
28 adjList[road[0]].add(road[1]);
29 adjList[road[1]].add(road[0]);
30 }
31 long[] cost = new long[1];
32 dfs(0, seats, cost);
33 return cost[0];
34 }
35
36 public static void main(String[] args) {
37 int[][] roads = {{3,1},{3,2},{1,0},{0,4},{0,5},{4,6}};
38 int seats = 2;
39 System.out.println(minimumFuelCost(roads, seats));
40 }
41}This Java solution initializes an adjacency list for the city network, invoked by DFS to compute fuel cost based on representatives managed by car seats. Each recursive call on DFS determines the amount of fuel needed by accommodating all available representatives.
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.