Checking whether a graph is bipartite using BFS

Question

I am solving a simple problem that checks whether a graph is two-colourable (bipartite graph). I am using BFS for this approach using C++ STL. I've replaced cin and cout with scanf and printf as suggested by fellow programmers but still the judge reports TLE.

#include<iostream>
#include<list>
#include<cstring>
#include<cstdio>
using namespace std;
int flag = 1;
class Graph
{
 int V;
 list<int> *adj;
 public:
 Graph(int V);
 void addEdge(int v, int w);
 void BFS(int s);
};
Graph::Graph(int V)
{
 this->V = V;
 adj = new list<int>[1000001];
}
void Graph::addEdge(int v, int w)
{
 adj[v].push_back(w);
 adj[w].push_back(v);
}
void Graph::BFS(int s)
{
 bool *visited = new bool[V];
 string *color = new string[1000001];
 for(int i=0;i<V;i++)
 visited[i] = false;
 list<int> queue;
 queue.push_back(s);
 visited[s] = true;
 color[s] = "red";
 list<int>::iterator i;
 flag = 1;
 while(!queue.empty())
 {
 s = queue.front();
 queue.pop_front();
 for(i = adj[s].begin(); i != adj[s].end(); i++)
 {
 if(!visited[*i])
 {
 visited[*i] = true;
 if(color[s] == "red")
 color[*i] = "blue";
 if(color[s] == "blue")
 color[*i] = "red";
 queue.push_back(*i);
 }
 else
 {
 if(color[s] == color[*i])
 flag = 0;
 }
 }
 }
}
int main()
{
 int T, bugs, edges, from, to;
 scanf("%d", &T);
 int p = T;
 while(T--)
 {
 scanf("%d%d", &bugs, &edges);
 Graph g(bugs+1);
 for(int i=0; i<edges; i++)
 {
 scanf("%d%d", &from, &to);
 g.addEdge(from, to);
 }
 g.BFS(from);
 if(!flag)
 printf("Scenario #%d:\nSuspicious bugs found!\n", p-T);
 else
 printf("Scenario #%d:\nNo suspicious bugs found!\n", p-T);
 }
 return 0;
}

• PaulMcKenzie: bool *visited = new bool[V]; string *color = new string[1000001]; This is a gigantic memory leak. using C++ STL. So why didn't you use std::vector here?
• Aaron McDaid: "replaced cin and cout with scanf and printf". You shouldn't have done that. You should look into ios_base::sync_with_stdio. In general, replacing C++ with C isn't going to speed things up. For a problem such as this, the C++ solution should be as fast as the C solution. Don't get distracted by language wars when you've got important issues to consider. Now you've got a bizarre mixture of C++ and C, which is going to be difficult for anybody to work with
• Matt: have you used any sort of code profiling tool like valgrind to look at where you code is spending time?
• Abhishek Kusnoor: I am not too comfortable with stl vectors. Although I know how to use them as simple arrays, I will have to do some reading on how to replace all list declarations by vectors. Blindly replacing list<int> by vector<int> doesn't seem to work. I will do some googling and get back!

Answer 1

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<int> *adj;

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

• andars: Note to keep the use of std::list for the queue.
• awesomeyi: @andars No, he should switch to std::queue
• andars: Sure, just don't change it to std::vector.
• user4581301: Anally retentive nag. Doubly linked list is the the most obvious std::list implementation candidate, but, if I remember correctly, not mandated. The only relevant requirements on std::list are for constant time insert and remove, and there is no requirement in list for speedy access, so it probably doesn't exist and the point holds.

Answer 2

In addition to what others have stated, another optimization is to remove doing things like this:

bool *visited = new bool[V];
string *color = new string[1000001];
for(int i=0;i<V;i++)
 visited[i] = false;

You do this each and every time the Graph::BFS function is called. Not only do you call the allocator each and every time, your function does not deallocate the memory, thus creating huge memory leaks.

Looking at your code, the better approach is to use vector and to move those items within your Graph class itself.

class Graph
{
 int V;
 list<int> *adj;
 std::vector<bool> visited;
 std::vector<std::string> color;
 public:
 Graph(int V);
 void addEdge(int v, int w);
 void BFS(int s);
};

and then:

#include <algorithm>
//...
void Graph::BFS(int s)
{
 visited.resize(V);
 color.resize(V);
 std::fill(visited.begin(), visited.end(), false);
 //...
}

This is more optimal and doesn't leak memory. Why is it more optimal? The only price you pay from the allocator is on the first call of BFS. A subsequent call will issue a resize, but vector is smart enough to not allocate any further memory, since the vector's have already been sized to V number of items.

• Abhishek Kusnoor: Thank you for the code! Now I understand better. Will try this out and resubmit.
• PaulMcKenzie: Well, I don't know if it will make the code fast enough to pass your test. But I can tell you that the code will be faster.
• Abhishek Kusnoor: I made changes exactly as you've suggested in the above anser. Everything working fine with the given test cases. This time its a segmentation fault but not TLE. Anything else that you can guess if the resize() thing? I am unable to understand the reason for memory issues even with the use of vectors. Thanks for your help!
• PaulMcKenzie: There are 2 issues with your code where you can lessen or eliminate segmentation faults. 1) Use std::vector<std::list<int>> instead of std::list<int>*. 2) Your for loops use indices within the vector's that may not be valid. For example, if you write a loop that goes from 0 to someVector.size(), then your index is safe to use only for someVector, not for another vector. Your loops use an index value meant for one vector, and then blindly uses it for other vectors in the loop.
• PaulMcKenzie: For example if(color[s] == "red") How do you know that s is a valid index? Maybe to ensure that you don't have an issue, that vector possibly should be a std::map<int, string>? Then even if you're "out of bounds", the worse that could happen is that you create an empty value in the map.

Answer 3

Instead of a std::list, use std::vector, as a std::vector provides fast random access(O(1)) but a std::list does not. Another thing you can do, although I am not sure if that would be completely relevant, is that instead of using new to allocate a bulk of memory in your constructor, re-write the functions so that you use push_back into your vector of vectors.

Answer 4

Use a 2D array (array of arrays) instead of a list as long as you know what the size will be from the beginning.