So compare the following codes and here is the question, SPOT THE REASON FOR THE DIFFERENCE IN TIME COMPLEXITIES in these 2 codes --

vector<vector<int>> adj_list;
queue<int> q;
vector[int] visited(n, 0);

q.push({source});
while (! q.empty()){
    int next = q.front();
    q.pop();
    visited[next] = 1; // <----
    for (int neigh: adj_list[next]){
        if (visited[neigh] != 1){
            q.add(neigh);
        }
    }
}

vector<vector<int>> adj_list;
queue<int> q;
vector[int] visited(n, 0);

q.push({source});
visited[source] = 1; // <----
while (! q.empty()){
    int next = q.front();
    q.pop();
    for (int neigh: adj_list[next]){
        if (visited[neigh] != 1){
            q.add(neigh);
            visited[neigh] = 1; // <----
        }
    }
}

Reason: Consider the example {{1, 2}, {1, 3}, {2, 3}} and {a, b} represents directed edge from a to b then 1 gets explored and 2 and 3 get added but neither one get marked as visitde in code-1 and so if 2 is explored next then 3 will again get added into the queue as 3 was never marked visited. And hence the time complexity goes from linear which is the one that people learn in school to Fibonacci form (I mean the recurrence transforms to represent a Fibonacci Sequence).

I am sharing this because it is something I never chose to question earlier and thanks to random solving and LC200 for helping this misconception of mine come to surface.