Checking whether a graph is bipartite using BFS
Stop using std::list, which is a doubly linked list and does not support fast random access. You should use std::vector instead, supporting O(1) random access.

Instead of 

list&lt;int&gt; *adj;


You can have a vector of vectors, which will be not only faster, but also memory-leak free.