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. I would appreciate any kind of improvement or efficiency on top of what I have done.

_Also as something to begin discussions in the comment section, could you share what you find to be the most exciting application of BFS as part of another problem or as part of your work (employment or research) etc. These little things give me a very good feeling inside when they are actually applied to solve something important.

I want to start blogging and start engaging with the community a little more. I am mostly an introvert in this aspect but still want to step out of my comfort and be better at understanding and conveying about what I think.

#include <iostream>

using namespace std;

int main(){
    cout << "Example Line" << endl;
}