815. Bus Routes
Tags:
Hard
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tìm số lượng xe bus tối thiểu cần thiết để đi từ source đến target → Thực chất đây là bài toán tìm đường đi ngắn nhất trong đồ thị, trong đó:
Approach
Solution: Using bus stops as Nodes
1// Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
2
3function numBusesToDestination(routes: number[][], source: number, target: number): number {
4 if(source === target) return 0;
5
6 const graph: Map<number, number[]> = new Map();
7
8 for(let i = 0; i < routes.length; i++) {
9 for(const stop of routes[i]) {
10 if(!graph.has(stop)) {
11 graph.set(stop, [])
12 }
13 graph.get(stop).push(i);
14 }
15 }
16
17 // queue: [current_stop, buses_taken]
18 const queue: [number, number][] = [[source, 0]]
19
20 const visited_stops: Set<number> = new Set([source]);
21 const visited_bus: Set<number> = new Set();
22
23 while(queue.length > 0) {
24 const [currennt_stop, bus_taken] = queue.shift()!;
25
26 if(current_stop === target) {
27 return bus_taken;
28 }
29
30 const stop_to_bus = graph.get(current_stop)! || [];
31 for(const bus of stop_to_bus) {
32 if(visited_stops.has(bus)) continue;
33
34 visited_bus.add(bus);
35
36 for(const next_stop of routes[bus]) {
37 if(!visite_stops.has(next_stop)) {
38 visited_stops.add(next_stop);
39 queue.push([next_stop, bus_taken + 1]);
40 }
41 }
42 }
43 }
44
45 return -1;
46}Solution: Using Routes as Node
1// Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
2
3function numBusesToDestination(routes: number[][], source: number, target: number): number {
4 if (source === target) return 0;
5
6 const n = routes.length;
7 const stop_to_buses: Map<number, number[]> = new Map();
8 for (let i = 0; i < n; i++) {
9 for (const stop of routes[i]) {
10 if (!stop_to_buses.has(stop)) {
11 stop_to_buses.set(stop, []);
12 }
13 stop_to_buses.get(stop)!.push(i)
14 }
15 }
16
17 /*
18 stop_to_bus:
19 1: [],
20 2: [],
21 7: [1],
22 3: [],
23 6: [],
24 */
25
26 const graph: Map<number, Set<number>> = new Map();
27 for (let i = 0; i < n; i++) {
28 graph.set(i, new Set());
29 }
30
31 for (const [stop, buses] of stop_to_buses.entries()) {
32 for (let i = 0; i < buses.length; i++) {
33 for (let j = i + 1; j < buses.length; j++) {
34 graph.get(buses[i])!.add(buses[j]);
35 graph.get(buses[j])!.add(buses[i]);
36 }
37 }
38 }
39
40 /*
41 graph = {
42 0: [1],
43 1: [0, 2],
44 2: [1]
45 }
46 */
47
48 const queue: [number, number][] = []; // [bus_index, bus_taken]
49 const visited_bus: Set<number> = new Set();
50
51 for (const bus of stop_to_buses.get(source) || []) {
52 queue.push([bus, 1]);
53 visited_bus.add(bus)
54 }
55
56 while (queue.length > 0) {
57 const [current_bus, bus_taken] = queue.shift()!;
58
59 for (const stop of routes[current_bus]) {
60 if (stop === target) {
61 return bus_taken;
62 }
63 }
64
65 for (const next_bus of graph.get(current_bus)!) {
66 if (!visited_bus.has(next_bus)) {
67 visited_bus.add(next_bus);
68 queue.push([next_bus, bus_taken + 1]);
69 }
70 }
71 }
72
73 return -1;
74}