Missing Test Case - 815. Bus Routes #2156
Description
Your LeetCode username
hqztrue
Category of the bug
- Question
- [√] Solution
- Language
Description of the bug
Two accepted solutions get Time Limit Exceeded on the following testcase:
https://github.com/hqztrue/shared_materials/blob/master/tmp/LeetCode/815.in
In particular, the second code has incorrect time complexity.
Code you used for Submit/Run operation
class Solution {
public:
struct Graph {
void Add(size_t s, size_t e) {
if (s == e) {
return;
}
if (!G.count(s)) {
G[s] = std::vector<size_t>();
}
G[s].emplace_back(e);
if (!G.count(s)) {
G[e] = std::vector<size_t>();
}
G[e].emplace_back(s);
}
const std::vector<size_t>& operator[](size_t index) const {
return G.at(index);
}
void Print() const {
for (auto p : G) {
std::cout << p.first << ":" << '\t';
for (auto n : p.second) {
std::cout << n << '\t';
}
std::cout << '\n';
}
}
bool empty() const noexcept {
return G.empty();
}
std::unordered_map<size_t, std::vector<size_t>> G;
};
int GetDist(const Graph& G, const std::unordered_set<size_t>& end, const std::unordered_set<size_t>& start) {
std::queue<std::pair<size_t, size_t>> q{};
std::unordered_set<size_t> visited{};
for (auto index : start) {
if (end.count(index)) {
return 1;
}
q.emplace(index, 1);
visited.emplace(index);
}
while (!q.empty()) {
auto t = std::move(q.front());
visited.emplace(t.first);
q.pop();
if (end.count(t.first)) {
return t.second;
}
for (auto node : G[t.first]) {
if (visited.count(node)) {
continue;
}
q.emplace(node, t.second + 1);
}
}
return -1;
}
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if (S == T) {
return 0;
}
std::unordered_set<size_t> start{}, end{};
Graph G;
for (size_t i{0}; i < routes.size(); i++) {
std::unordered_set<size_t> stops;
for (size_t k{0}; k < routes[i].size(); k++) {
if (routes[i][k] == S) {
start.emplace(i);
} else if (routes[i][k] == T) {
end.emplace(i);
}
stops.emplace(routes[i][k]);
}
for (size_t j{i + 1}; j < routes.size(); j++) {
for (size_t k{0}; k < routes[j].size(); k++) {
if (stops.count(routes[j][k])) {
G.Add(i, j);
}
}
}
}
// G.Print();
if (G.empty()) {
return -1;
}
return GetDist(G, end, start);
}
};
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
unordered_map<int,vector<int>> m;
if(S==T){ return 0;}
int n = routes.size();
for(int i=0;i<n;i++){
for(int v: routes[i]){
m[v].push_back(i);
}
}
unordered_set<int> vis;
unordered_set<int> stationVis;
queue<pair<int,int>> bfs;
bfs.push({S,1});
stationVis.insert(S);
for(int route: m[S]){
vis.insert(route);
for(int v: routes[route]){
if(stationVis.find(v)==vis.end()){
bfs.push({v,1});
stationVis.insert(v);
}
}
}
while(!bfs.empty()){
auto t = bfs.front();
int v = t.first;
int count = t.second;
bfs.pop();
if(v==T){ return count;}
for(int route: m[v]){
if(vis.find(route)==vis.end()){
//vis.insert(route); //add this line to fix the time complexity
for(int st: routes[route]){
if(stationVis.find(st)==stationVis.end()){
bfs.push({st,count+1});
stationVis.insert(st);
}
}
}
}
}
return -1;
}
};
Language used for code
C++
Expected behavior
The two codes get Time Limit Exceeded.
Screenshots
Additional context
Here's a smaller input generated using the same logic, that can only make the second code TLE. You can choose to add either testcase.
https://github.com/hqztrue/shared_materials/blob/master/tmp/LeetCode/815_2.in