Program works fine only for one test case - Debugging

Question!

I want to know whether my graph is bipartite or not, I have several test cases. If I run more than one test case it doesn't work properly, it always shows Bipartite. I am having a hard time figuring it out. For just one case, it works fine for any graph.
Here goes my code.

#include <iostream>
#include <cstdio>
#include <stack>
#include <list>

using namespace std;

class Graph
{
    public:
        int V;
        list<int> *adj;
        Graph(int V);
        void addEdge(int v, int w);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

class Bipartite
{
    private:
        bool isBipartite;
        bool *color;
        bool *marked;
        int *edgeTo;
        stack<int> cycle;
    public:
        Bipartite(Graph G)
        {
            isBipartite = true;
            color = new bool [G.V];
            marked = new bool [G.V];
            edgeTo = new int [G.V];
            for (int v = 0; v < G.V; v++)
            {
                if (!marked[v])
                {
                    color[v] = false;
                    dfs(G, v);
                }
            }

            delete color;
            delete marked;
            delete edgeTo;
        }

        void dfs(Graph G, int v)
        {
            marked[v] = true;
            list<int>::iterator w;
            for (w = G.adj[v].begin(); w != G.adj[v].end(); w++)
            {
                if (!cycle.empty())
                    return;
                if (!marked[*w])
                {
                    edgeTo[*w] = v;
                    color[*w] = !color[v];
                    dfs(G, *w);
                }
                else if (color[*w] == color[v])
                {
                    isBipartite = false;
                    cycle.push(*w);
                    for (int x = v; x != *w; x = edgeTo[x])
                    {
                        cycle.push(x);
                    }
                    cycle.push(*w);
                }
            }
        }

        bool isBi()
        {
            return isBipartite;
        }
};

void solve(int n,int **p){
    long long int x,y;
    Graph g(n);

    for(x=0;x<n;x++)
        for(y=0;y<n;y++)
        {
            if(p[x][y]==1)
                g.addEdge(x,y);
        }

    Bipartite b(g);
    if (b.isBi())
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

int main()
{

    long long int i,j,t,x,m,y,a,b;
    int **p,n;

    cin>>t;

    for(i=0;i<t;i++)
    {
        cin>>n>>m;

        p=new int*[n]();
        for(x=0;x<n;x++)
        {
            p[x]=new int[n]();
        }

        for(j=0;j<m;j++)
        {
            cin>>a>>b;
            a=a-1;
            b=b-1;

            p[a][b]=1;
            p[b][a]=1;

        }

        for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)
            {
                if(x!=y)
                {
                    p[x][y]=1-p[x][y];
                }
            }
        }

        /*  for(x=0;x<n;x++)
        {
            for(y=0;y<n;y++)
                cout<<p[x][y]<<" ";
            cout<<"\n";
        }
        */

        solve(n,p);
    }
    return 0;
}
By : Born2Code


Answers

Also Bipartite(Graph G) is calling the default copy constructor of Graph. Probably not what you want.

Try Bipartite(const Graph & G) instead (also in dfs).

And don't do new without delete.

Rather use vector<vector<int>> adj;, why even list? And reinit it in constructor with adj.resize(V);.


After your edit of code in question, as you use new to allocate array, you should delete it as array too, so use delete[] color;.

Or stop using new/delete completely. Again you can use std::vector<bool> color(G.V);, avoiding both new/delete hassle, and also having all values initialized to false by default.

In modern C++ there're very few (more like "none") reasons to ever use new or delete (unless you write some low level library, or you are optimizing for performance, and you know what you are doing).

By : Ped7g


You never explicitly initialize the contents of marked, or, more accurately, the contents of the array that it points to.

The loop in your constructor reads elements of marked to decide how to assign to color, but you never initialized the elements of marked being read.

Similiar argument for color and edgeTo.

This means that, while they may have had the expected initializations for the first case, may well be using whatever value happened to be there in later cases.



The descriptions are mandatory for any content you or any frameworks you link against attempt to access. The errors are generated upon an attempt to access the content if a usage description was not supplied, so if you're getting those errors your app must be requesting them. You should discover why your app or its frameworks require these and add appropriate usage descriptions to your app's info.plist.

Or more ideally, if you don't need access, see if there's a way to not request it (or use frameworks that do unnecessarily).



This video can help you solving your question :)
By: admin