Bus Routes

815. Bus Routes

complexity : O(n)

Topic: BFS

 Eplanation

class Solution {
    #include<bits/stdc++.h>
public:
    int numBusesToDestination(vector<vector<int> >& routes, int S, int T)
{
    unordered_map<int, unordered_set<int> > stop_routes;

    for(int i = 0; i < routes.size(); i++){
        for(int j : routes[i])stop_routes[j].insert(i);
    }

    queue<pair<int, int> > to_visit;
    to_visit.push({S,0});
    unordered_set<int>stop_visited = { S };

    while(!to_visit.empty()){
        int stop = to_visit.front().first;
        int bus_n = to_visit.front().second;

        if(stop == T)return bus_n;

        to_visit.pop();

        for(const auto& route : stop_routes[stop]){
            for(const auto& next_stop : routes[route]){
                auto it = stop_visited.insert(next_stop);
                if(it.second)to_visit.push({next_stop, bus_n+1});
            }
            routes[route].clear();
        }
    }
        return -1;
}
};

Share: