Breadth-First Search
Array
Hash Table
Description
You are given an array routes
representing bus routes where routes[i]
is a bus route that the ith
bus repeats forever.
For example, if routes[0] = [1, 5, 7]
, this means that the 0th
bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...
forever.
You will start at the bus stop source
(You are not on any bus initially), and you want to go to the bus stop target
. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source
to target
. Return -1
if it is not possible.
Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
Constraints:
1 <= routes.length <= 500
.
1 <= routes[i].length <= 105
All the values of routes[i]
are unique .
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
Solutions
Solution 1
Python3 Java C++ Go C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution :
def numBusesToDestination (
self , routes : List [ List [ int ]], source : int , target : int
) -> int :
if source == target :
return 0
# 一条公交线路有哪些公交站
s = [ set ( r ) for r in routes ]
# 一个公交站在哪些公交线路有
d = defaultdict ( list )
for i , r in enumerate ( routes ):
for v in r :
d [ v ] . append ( i )
g = defaultdict ( list )
for ids in d . values ():
m = len ( ids )
for i in range ( m ):
for j in range ( i + 1 , m ):
a , b = ids [ i ], ids [ j ]
g [ a ] . append ( b )
g [ b ] . append ( a )
q = deque ( d [ source ])
ans = 1
vis = set ( d [ source ])
while q :
for _ in range ( len ( q )):
i = q . popleft ()
if target in s [ i ]:
return ans
for j in g [ i ]:
if j not in vis :
vis . add ( j )
q . append ( j )
ans += 1
return - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 class Solution {
public int numBusesToDestination ( int [][] routes , int source , int target ) {
if ( source == target ) {
return 0 ;
}
int n = routes . length ;
Set < Integer >[] s = new Set [ n ] ;
List < Integer >[] g = new List [ n ] ;
Arrays . setAll ( s , k -> new HashSet <> ());
Arrays . setAll ( g , k -> new ArrayList <> ());
Map < Integer , List < Integer >> d = new HashMap <> ();
for ( int i = 0 ; i < n ; ++ i ) {
for ( int v : routes [ i ] ) {
s [ i ] . add ( v );
d . computeIfAbsent ( v , k -> new ArrayList <> ()). add ( i );
}
}
for ( var ids : d . values ()) {
int m = ids . size ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = i + 1 ; j < m ; ++ j ) {
int a = ids . get ( i ), b = ids . get ( j );
g [ a ] . add ( b );
g [ b ] . add ( a );
}
}
}
Deque < Integer > q = new ArrayDeque <> ();
Set < Integer > vis = new HashSet <> ();
int ans = 1 ;
for ( int v : d . get ( source )) {
q . offer ( v );
vis . add ( v );
}
while ( ! q . isEmpty ()) {
for ( int k = q . size (); k > 0 ; -- k ) {
int i = q . pollFirst ();
if ( s [ i ] . contains ( target )) {
return ans ;
}
for ( int j : g [ i ] ) {
if ( ! vis . contains ( j )) {
vis . add ( j );
q . offer ( j );
}
}
}
++ ans ;
}
return - 1 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 class Solution {
public :
int numBusesToDestination ( vector < vector < int >>& routes , int source , int target ) {
if ( source == target ) {
return 0 ;
}
int n = routes . size ();
vector < unordered_set < int >> s ( n );
vector < vector < int >> g ( n );
unordered_map < int , vector < int >> d ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int v : routes [ i ]) {
s [ i ]. insert ( v );
d [ v ]. push_back ( i );
}
}
for ( auto & [ _ , ids ] : d ) {
int m = ids . size ();
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = i + 1 ; j < m ; ++ j ) {
int a = ids [ i ], b = ids [ j ];
g [ a ]. push_back ( b );
g [ b ]. push_back ( a );
}
}
}
queue < int > q ;
unordered_set < int > vis ;
int ans = 1 ;
for ( int v : d [ source ]) {
q . push ( v );
vis . insert ( v );
}
while ( ! q . empty ()) {
for ( int k = q . size (); k ; -- k ) {
int i = q . front ();
q . pop ();
if ( s [ i ]. count ( target )) {
return ans ;
}
for ( int j : g [ i ]) {
if ( ! vis . count ( j )) {
vis . insert ( j );
q . push ( j );
}
}
}
++ ans ;
}
return -1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 func numBusesToDestination ( routes [][] int , source int , target int ) int {
if source == target {
return 0
}
n := len ( routes )
s := make ([] map [ int ] bool , n )
g := make ([][] int , n )
d := map [ int ][] int {}
for i , r := range routes {
for _ , v := range r {
if s [ i ] == nil {
s [ i ] = make ( map [ int ] bool )
}
s [ i ][ v ] = true
d [ v ] = append ( d [ v ], i )
}
}
for _ , ids := range d {
m := len ( ids )
for i := 0 ; i < m ; i ++ {
for j := i + 1 ; j < m ; j ++ {
a , b := ids [ i ], ids [ j ]
g [ a ] = append ( g [ a ], b )
g [ b ] = append ( g [ b ], a )
}
}
}
q := d [ source ]
vis := map [ int ] bool {}
for _ , v := range d [ source ] {
vis [ v ] = true
}
ans := 1
for len ( q ) > 0 {
for k := len ( q ); k > 0 ; k -- {
i := q [ 0 ]
q = q [ 1 :]
if s [ i ][ target ] {
return ans
}
for _ , j := range g [ i ] {
if ! vis [ j ] {
vis [ j ] = true
q = append ( q , j )
}
}
}
ans ++
}
return - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 public class Solution {
public int NumBusesToDestination ( int [][] routes , int source , int target ) {
if ( source == target ) {
return 0 ;
}
Dictionary < int , HashSet < int >> stopToRoutes = new Dictionary < int , HashSet < int >> ();
List < HashSet < int >> routeToStops = new List < HashSet < int >> ();
for ( int i = 0 ; i < routes . Length ; i ++ ) {
routeToStops . Add ( new HashSet < int > ());
foreach ( int stop in routes [ i ]) {
routeToStops [ i ]. Add ( stop );
if ( ! stopToRoutes . ContainsKey ( stop )) {
stopToRoutes [ stop ] = new HashSet < int > ();
}
stopToRoutes [ stop ]. Add ( i );
}
}
Queue < int > queue = new Queue < int > ();
HashSet < int > visited = new HashSet < int > ();
int ans = 0 ;
foreach ( int routeId in stopToRoutes [ source ]) {
queue . Enqueue ( routeId );
visited . Add ( routeId );
}
while ( queue . Count > 0 ) {
int count = queue . Count ;
ans ++ ;
for ( int i = 0 ; i < count ; i ++ ) {
int routeId = queue . Dequeue ();
foreach ( int stop in routeToStops [ routeId ]) {
if ( stop == target ) {
return ans ;
}
foreach ( int nextRoute in stopToRoutes [ stop ]) {
if ( ! visited . Contains ( nextRoute )) {
visited . Add ( nextRoute );
queue . Enqueue ( nextRoute );
}
}
}
}
}
return - 1 ;
}
}