Bus Routes LeetCode solution in C++

1
class Solution {
2
 public:
3
  int numBusesToDestination(vector<vector<int>> &routes, int source, int target) {
4
    if (source == target) return 0;
5
    queue<int> q;
6
    vector<bool> vis(routes.size(), 0);
7
    vector<vector<int>> g(routes.size());
8
    vector<unordered_set<int>> rout(routes.size());
9

10
    // create graph between the buses - which buses are connected to single stop
11
    for (int i = 0; i < routes.size(); ++i) {
12
      for (auto r : routes[i]) {
13
        rout[i].insert(r);
14
        for (int j = 0; j < i; ++j) {
15
          if (rout[j].find(r) != rout[j].end()) {
16
            g[i].push_back(j);
17
            g[j].push_back(i);
18
          }
19
        }
20
      }
21
      if (rout[i].find(source) != rout[i].end()) {
22
        q.push(i);
23
        vis[i] = true;
24
      }
25
    }
26

27
    // search path to target using bfs
28
    int level = 0;
29
    while (!q.empty()) {
30
      int n = q.size();
31
      level++;
32
      while (n--) {
33
        int node = q.front();
34
        q.pop();
35
        if (rout[node].find(target) != rout[node].end()) return level;
36
        for (auto i : g[node]) {
37
          if (vis[i] == false) {
38
            q.push(i);
39
            vis[i] = true;
40
          }
41
        }
42
      }
43
    }
44
    return -1;
45
  }
46
};