1
\$\begingroup\$

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;
}
\$\endgroup\$
4
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ Jul 21, 2015 at 20:22
  • 1
    \$\begingroup\$ "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 \$\endgroup\$ Jul 21, 2015 at 20:23
  • \$\begingroup\$ have you used any sort of code profiling tool like valgrind to look at where you code is spending time? \$\endgroup\$
    – Matt
    Jul 21, 2015 at 20:27
  • \$\begingroup\$ 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! \$\endgroup\$
    – Abhishek Kusnoor
    Jul 21, 2015 at 20:35

4 Answers 4

3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Note to keep the use of std::list for the queue. \$\endgroup\$
    – andars
    Jul 21, 2015 at 20:25
  • \$\begingroup\$ @andars No, he should switch to std::queue \$\endgroup\$
    – awesomeyi
    Jul 21, 2015 at 20:26
  • \$\begingroup\$ Sure, just don't change it to std::vector. \$\endgroup\$
    – andars
    Jul 21, 2015 at 20:32
  • \$\begingroup\$ 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. \$\endgroup\$
    – user4581301
    Jul 21, 2015 at 21:01
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the code! Now I understand better. Will try this out and resubmit. \$\endgroup\$
    – Abhishek Kusnoor
    Jul 21, 2015 at 20:39
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 21, 2015 at 20:43
  • \$\begingroup\$ 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! \$\endgroup\$ Jul 22, 2015 at 17:00
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 22, 2015 at 22:52
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 22, 2015 at 22:57
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.