815. Bus Routes

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}

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}