題目連結：
題目意譯：
你被給定一個代表著公車路線的陣列 routes，其中 routes[i] 為第 i 台公車會一直重複行駛的路線。
例如說，如果 routes[0] = [1, 5, 7]，這代表著第 0 台公車將以序列 1 → 5 → 7 → 1 → 5 → 7 → 1 → … 一直不斷地行駛下去。
你一開始位於公車站牌 source（你最初不在任何公車上），而你想要到達公車站牌 target。你只能藉由公車在公車站牌之間移動。
回傳從 source 到 target 最少所需要搭乘的公車數量。如果這不可能辦到，則回傳 -1。
限制：
1 ≦ routes.length ≦ 500.
1 ≦ routes[i].length ≦ 10 ^ 5
routes[i] 中的數值彼此相異。
sum(routes[i].length) ≦ 10 ^ 5
0 ≦ routes[i][j] < 10 ^ 6
0 ≦ source, target < 10 ^ 6
範例測資：
範例 1：
輸入： routes = [[1,2,7],[3,6,7]], source = 1, target = 6
輸出： 2
解釋： 最佳策略為搭乘第一台公車到 7 號站牌，接著搭乘第二台到 6 號站牌。
範例 2：
輸入： routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
輸出： -1
解題思維：
假設現在我們知道所有數對 (i, j)，使得搭公車 i 可以轉乘公車 j（也就是說，公車 i 和 j 有相同的公車站牌），則此時實際上本題就變成類似迷宮問題（如這題）之題型。因此我們這時候只需要從站牌 source 進行廣度優先搜尋（Breadth First Search，BFS）一步一步地擴散即可以最少步數抵達 target。
但問題是我們不知道任何一對 (i, j)，所以我們需要自行先把公車與公車互通（轉乘）的關係給建立出來。方式很簡單：
用一個雜湊表（Hash Table）H 來記錄每一個站牌有哪些公車通行。因此我們掃過所有路線把 H 的內容建立出來。
接著對於每一個站牌，把有通行於該站牌的所有公車彼此建立出互通的關係（即可以互相轉乘）。所有站牌掃完之後我們便知道所有上述所提及的數對 (i, j)。
而這個步驟表面上看起來將會花上 O(|H| × n ^ 2)，其中 |H| 為 H 之大小（即站牌總數）、n 為 routes 之大小（即公車數）。但是由於題目給定了 sum(routes[i].length) ≦ 10 ^ 5 這個條件，所以單一公車路線有很多站牌則會限制其他公車與其互通的機會。
因此我們可以看到最糟的時間將會出現於 n 部公車的路線全部長一模一樣的情況下。因此最糟時間複雜度為 O((10 ^ 5 ÷ n) × n ^ 2) = O(10 ^ 5 × n)，其實是還行的。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
